Submission #1370771


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(...) _dbg(#__VA_ARGS__",", __VA_ARGS__)
void _dbg(string){cout<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cout<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

#define INF 1120000000
#define MOD 1000000007

long dp[2][610][610];

long solve(){
  int n,m;
  cin>>n>>m;
  vector<pair<int,int>> vec(m);
  rep(i,m) cin>>vec[i].fi>>vec[i].se;

  vector<int> imos(n+1, 0);
  rep(i,m)imos[vec[i].fi-1]++, imos[vec[i].se]--;
  rep(i,n) imos[i+1] += imos[i];
  assert(imos[n]==0);
  rep(i,n) if(imos[i]<2) return 0;

  vector<int> nums;
  rep(i,m) nums.pb(vec[i].fi-1), nums.pb(vec[i].fi), nums.pb(vec[i].se);
  nums.pb(0);
  uniq(nums);
  rep(i,m){
    vec[i].fi = lower_bound(all(nums), vec[i].fi) - nums.begin();
    vec[i].se = lower_bound(all(nums), vec[i].se) - nums.begin();
  }
  sort(all(vec));
//dbg(vec,m);
  n = nums.size();
  auto crnt = dp[0];
  auto prev = dp[1];
  fill(prev[0], prev[n+1], 0);
  prev[0][0] = 1;
  rep(i,m){//dbg(i);
    for(int j=vec[i].fi-1; j<=vec[i].se; j++){
      for(int k=vec[i].fi-1; k<=j; k++)
        crnt[j][vec[i].se] += prev[k][j];
    }
    for(int j=vec[i].se+1; j<n; j++){
      for(int k=vec[i].fi-1; k<=j; k++)
        crnt[max(vec[i].se,k)][j] += prev[k][j];
    }
    rep(j,n)rep(k,n) crnt[j][k] = (crnt[j][k] + prev[j][k])%MOD;
    swap(crnt, prev);
  }
  return prev[n-1][n-1];
}

int main(){
  cout << solve() << endl;

  return 0;
}

Submission Info

Submission Time
Task H - ダイヤグラム
User tossy
Language C++14 (GCC 5.4.1)
Score 0
Code Size 2077 Byte
Status WA
Exec Time 181 ms
Memory 6016 KB

Judge Result

Set Name small medium large
Score / Max Score 0 / 10 0 / 40 0 / 50
Status
AC × 12
WA × 12
AC × 12
WA × 33
AC × 14
WA × 61
Set Name Test Cases
small small/case_000.txt, small/case_001.txt, small/case_002.txt, small/case_003.txt, small/case_004.txt, small/case_005.txt, small/case_006.txt, small/case_007.txt, small/case_008.txt, small/case_009.txt, small/case_010.txt, small/case_011.txt, small/case_012.txt, small/case_013.txt, small/case_014.txt, small/case_015.txt, small/case_016.txt, small/case_017.txt, small/case_018.txt, small/case_019.txt, small/case_020.txt, small/case_021.txt, small/case_022.txt, small/case_023.txt
medium medium/case_000.txt, medium/case_001.txt, medium/case_002.txt, medium/case_003.txt, medium/case_004.txt, medium/case_005.txt, medium/case_006.txt, medium/case_007.txt, medium/case_008.txt, medium/case_009.txt, medium/case_010.txt, medium/case_011.txt, medium/case_012.txt, medium/case_013.txt, medium/case_014.txt, medium/case_015.txt, medium/case_016.txt, medium/case_017.txt, medium/case_018.txt, medium/case_019.txt, medium/case_020.txt, medium/case_021.txt, medium/case_022.txt, medium/case_023.txt, medium/medium_case_000.txt, medium/medium_case_001.txt, medium/medium_case_002.txt, medium/medium_case_003.txt, medium/medium_case_004.txt, medium/medium_case_005.txt, medium/medium_case_006.txt, medium/medium_case_007.txt, medium/medium_case_008.txt, medium/medium_case_009.txt, medium/medium_case_010.txt, medium/medium_case_011.txt, medium/medium_case_012.txt, medium/medium_case_013.txt, medium/medium_case_014.txt, medium/medium_case_015.txt, medium/medium_case_016.txt, medium/medium_case_017.txt, medium/medium_case_018.txt, medium/medium_case_019.txt, medium/medium_case_020.txt
large large/case_000.txt, large/case_001.txt, large/case_002.txt, large/case_003.txt, large/case_004.txt, large/case_005.txt, large/case_006.txt, large/case_007.txt, large/case_008.txt, large/case_009.txt, large/case_010.txt, large/case_011.txt, large/case_012.txt, large/case_013.txt, large/case_014.txt, large/case_015.txt, large/case_016.txt, large/case_017.txt, large/case_018.txt, large/case_019.txt, large/case_020.txt, large/case_021.txt, large/case_022.txt, large/case_023.txt, large/large_case_000.txt, large/large_case_001.txt, large/large_case_002.txt, large/large_case_003.txt, large/large_case_004.txt, large/large_case_005.txt, large/large_case_006.txt, large/large_case_007.txt, large/large_case_008.txt, large/large_case_009.txt, large/large_case_010.txt, large/large_case_011.txt, large/large_case_012.txt, large/large_case_013.txt, large/large_case_014.txt, large/large_case_015.txt, large/large_case_016.txt, large/large_case_017.txt, large/large_case_018.txt, large/large_case_019.txt, large/large_case_020.txt, large/large_case_021.txt, large/large_case_022.txt, large/large_case_023.txt, large/large_case_024.txt, large/large_case_025.txt, large/large_case_026.txt, large/large_case_027.txt, large/large_case_028.txt, large/large_case_029.txt, large/medium_case_000.txt, large/medium_case_001.txt, large/medium_case_002.txt, large/medium_case_003.txt, large/medium_case_004.txt, large/medium_case_005.txt, large/medium_case_006.txt, large/medium_case_007.txt, large/medium_case_008.txt, large/medium_case_009.txt, large/medium_case_010.txt, large/medium_case_011.txt, large/medium_case_012.txt, large/medium_case_013.txt, large/medium_case_014.txt, large/medium_case_015.txt, large/medium_case_016.txt, large/medium_case_017.txt, large/medium_case_018.txt, large/medium_case_019.txt, large/medium_case_020.txt
Case Name Status Exec Time Memory
large/case_000.txt AC 2 ms 2304 KB
large/case_001.txt AC 1 ms 256 KB
large/case_002.txt AC 2 ms 2304 KB
large/case_003.txt AC 2 ms 2304 KB
large/case_004.txt AC 2 ms 2304 KB
large/case_005.txt AC 2 ms 2304 KB
large/case_006.txt AC 1 ms 256 KB
large/case_007.txt AC 1 ms 256 KB
large/case_008.txt AC 1 ms 256 KB
large/case_009.txt AC 2 ms 2304 KB
large/case_010.txt AC 2 ms 2304 KB
large/case_011.txt AC 2 ms 2304 KB
large/case_012.txt WA 2 ms 2304 KB
large/case_013.txt WA 2 ms 2304 KB
large/case_014.txt WA 2 ms 2304 KB
large/case_015.txt WA 2 ms 2304 KB
large/case_016.txt WA 2 ms 2304 KB
large/case_017.txt WA 2 ms 2304 KB
large/case_018.txt WA 2 ms 2304 KB
large/case_019.txt WA 2 ms 2304 KB
large/case_020.txt WA 2 ms 2304 KB
large/case_021.txt WA 2 ms 2304 KB
large/case_022.txt WA 2 ms 2304 KB
large/case_023.txt WA 2 ms 2304 KB
large/large_case_000.txt WA 181 ms 6016 KB
large/large_case_001.txt WA 178 ms 6016 KB
large/large_case_002.txt WA 170 ms 5888 KB
large/large_case_003.txt WA 175 ms 5888 KB
large/large_case_004.txt WA 171 ms 5888 KB
large/large_case_005.txt WA 167 ms 5888 KB
large/large_case_006.txt WA 176 ms 6016 KB
large/large_case_007.txt WA 161 ms 5888 KB
large/large_case_008.txt WA 169 ms 5888 KB
large/large_case_009.txt WA 179 ms 6016 KB
large/large_case_010.txt WA 19 ms 3200 KB
large/large_case_011.txt WA 19 ms 3200 KB
large/large_case_012.txt AC 1 ms 256 KB
large/large_case_013.txt WA 17 ms 3200 KB
large/large_case_014.txt WA 18 ms 3200 KB
large/large_case_015.txt WA 18 ms 3200 KB
large/large_case_016.txt WA 19 ms 3200 KB
large/large_case_017.txt WA 18 ms 3200 KB
large/large_case_018.txt WA 19 ms 3200 KB
large/large_case_019.txt AC 1 ms 256 KB
large/large_case_020.txt WA 177 ms 6016 KB
large/large_case_021.txt WA 174 ms 5888 KB
large/large_case_022.txt WA 176 ms 6016 KB
large/large_case_023.txt WA 171 ms 6016 KB
large/large_case_024.txt WA 173 ms 5888 KB
large/large_case_025.txt WA 178 ms 6016 KB
large/large_case_026.txt WA 177 ms 6016 KB
large/large_case_027.txt WA 172 ms 5888 KB
large/large_case_028.txt WA 167 ms 5888 KB
large/large_case_029.txt WA 180 ms 6016 KB
large/medium_case_000.txt WA 2 ms 2432 KB
large/medium_case_001.txt WA 2 ms 2432 KB
large/medium_case_002.txt WA 2 ms 2432 KB
large/medium_case_003.txt WA 2 ms 2432 KB
large/medium_case_004.txt WA 2 ms 2432 KB
large/medium_case_005.txt WA 2 ms 2432 KB
large/medium_case_006.txt WA 2 ms 2432 KB
large/medium_case_007.txt WA 2 ms 2432 KB
large/medium_case_008.txt WA 2 ms 2432 KB
large/medium_case_009.txt WA 2 ms 2432 KB
large/medium_case_010.txt WA 2 ms 2432 KB
large/medium_case_011.txt WA 2 ms 2432 KB
large/medium_case_012.txt WA 2 ms 2432 KB
large/medium_case_013.txt WA 2 ms 2432 KB
large/medium_case_014.txt WA 2 ms 2432 KB
large/medium_case_015.txt WA 2 ms 2304 KB
large/medium_case_016.txt WA 2 ms 2432 KB
large/medium_case_017.txt WA 2 ms 2432 KB
large/medium_case_018.txt WA 2 ms 2432 KB
large/medium_case_019.txt WA 2 ms 2304 KB
large/medium_case_020.txt WA 2 ms 2304 KB
medium/case_000.txt AC 2 ms 2304 KB
medium/case_001.txt AC 1 ms 256 KB
medium/case_002.txt AC 2 ms 2304 KB
medium/case_003.txt AC 2 ms 2304 KB
medium/case_004.txt AC 2 ms 2304 KB
medium/case_005.txt AC 2 ms 2304 KB
medium/case_006.txt AC 1 ms 256 KB
medium/case_007.txt AC 1 ms 256 KB
medium/case_008.txt AC 1 ms 256 KB
medium/case_009.txt AC 2 ms 2304 KB
medium/case_010.txt AC 2 ms 2304 KB
medium/case_011.txt AC 2 ms 2304 KB
medium/case_012.txt WA 2 ms 2304 KB
medium/case_013.txt WA 2 ms 2304 KB
medium/case_014.txt WA 2 ms 2304 KB
medium/case_015.txt WA 2 ms 2304 KB
medium/case_016.txt WA 2 ms 2304 KB
medium/case_017.txt WA 2 ms 2304 KB
medium/case_018.txt WA 2 ms 2304 KB
medium/case_019.txt WA 2 ms 2304 KB
medium/case_020.txt WA 2 ms 2304 KB
medium/case_021.txt WA 2 ms 2304 KB
medium/case_022.txt WA 2 ms 2304 KB
medium/case_023.txt WA 2 ms 2304 KB
medium/medium_case_000.txt WA 2 ms 2432 KB
medium/medium_case_001.txt WA 2 ms 2432 KB
medium/medium_case_002.txt WA 2 ms 2432 KB
medium/medium_case_003.txt WA 2 ms 2432 KB
medium/medium_case_004.txt WA 2 ms 2432 KB
medium/medium_case_005.txt WA 2 ms 2432 KB
medium/medium_case_006.txt WA 2 ms 2432 KB
medium/medium_case_007.txt WA 2 ms 2432 KB
medium/medium_case_008.txt WA 2 ms 2432 KB
medium/medium_case_009.txt WA 2 ms 2432 KB
medium/medium_case_010.txt WA 2 ms 2432 KB
medium/medium_case_011.txt WA 2 ms 2432 KB
medium/medium_case_012.txt WA 2 ms 2432 KB
medium/medium_case_013.txt WA 2 ms 2432 KB
medium/medium_case_014.txt WA 2 ms 2432 KB
medium/medium_case_015.txt WA 2 ms 2304 KB
medium/medium_case_016.txt WA 2 ms 2432 KB
medium/medium_case_017.txt WA 2 ms 2432 KB
medium/medium_case_018.txt WA 2 ms 2432 KB
medium/medium_case_019.txt WA 2 ms 2304 KB
medium/medium_case_020.txt WA 2 ms 2304 KB
small/case_000.txt AC 2 ms 2304 KB
small/case_001.txt AC 1 ms 256 KB
small/case_002.txt AC 2 ms 2304 KB
small/case_003.txt AC 2 ms 2304 KB
small/case_004.txt AC 2 ms 2304 KB
small/case_005.txt AC 2 ms 2304 KB
small/case_006.txt AC 1 ms 256 KB
small/case_007.txt AC 1 ms 256 KB
small/case_008.txt AC 1 ms 256 KB
small/case_009.txt AC 2 ms 2304 KB
small/case_010.txt AC 2 ms 2304 KB
small/case_011.txt AC 2 ms 2304 KB
small/case_012.txt WA 2 ms 2304 KB
small/case_013.txt WA 2 ms 2304 KB
small/case_014.txt WA 2 ms 2304 KB
small/case_015.txt WA 2 ms 2304 KB
small/case_016.txt WA 2 ms 2304 KB
small/case_017.txt WA 2 ms 2304 KB
small/case_018.txt WA 2 ms 2304 KB
small/case_019.txt WA 2 ms 2304 KB
small/case_020.txt WA 2 ms 2304 KB
small/case_021.txt WA 2 ms 2304 KB
small/case_022.txt WA 2 ms 2304 KB
small/case_023.txt WA 2 ms 2304 KB