# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
29329 | 2017-07-19T02:41:49 Z | 서규호(#1166) | Meteors (POI11_met) | C++14 | 6000 ms | 63136 KB |
#include <bits/stdc++.h> #include <unistd.h> #define pii pair<int,int> #define pll pair<lld,lld> #define pb push_back #define next nextt #define left leftt #define right rightt #define lld long long #define Inf 1000000000 #define Mod 1000000007 #define Linf 1000000000000000000LL #define get gett using namespace std; const int bsize = 17000; int N,M,K; int a[300002],need[300002]; int x[300002],y[300002],z[300002]; lld cnt[(300000/bsize)+2][300002]; vector<int> memo[300002]; int get(int it,int color){ int l,r,tmp; if(memo[color].size() == 0 || it < memo[color][0]) return 0; l = 0; r = memo[color].size()-1; while(l <= r){ int m = (l+r)/2; if(it >= memo[color][m]){ tmp = m+1; l = m+1; }else r = m-1; } return tmp; } int main(){ //freopen("input.txt","r",stdin); scanf("%d %d",&N,&M); for(int i=1; i<=M; i++){ scanf("%d",&a[i]); memo[a[i]].pb(i); } for(int i=1; i<=N; i++) scanf("%d",&need[i]); scanf("%d",&K); for(int i=1; i<=K; i++){ scanf("%d %d %d",&x[i],&y[i],&z[i]); if(x[i] <= y[i]){ cnt[i/bsize][x[i]]+=z[i]; cnt[i/bsize][y[i]+1]-=z[i]; }else{ cnt[i/bsize][1]+=z[i]; cnt[i/bsize][y[i]+1]-=z[i]; cnt[i/bsize][x[i]]+=z[i]; } } for(int i=1/bsize; i<=K/bsize; i++){ for(int j=1; j<=M; j++){ cnt[i][j] += cnt[i][j-1]; cnt[K/bsize+1][j] = cnt[i][j]; } for(int j=1; j<=N; j++) cnt[i][j] = 0; for(int j=1; j<=M; j++){ cnt[i][a[j]] += cnt[K/bsize+1][j]; cnt[i][a[j]] = min(cnt[i][a[j]],(lld)Inf); } } for(int i=1; i<=N; i++){ lld sum = 0; int s = 0,e; for(int j=1/bsize; j<=K/bsize; j++){ sum += cnt[j][i]; if(sum >= need[i]){ s = max(1,j*bsize); e = min((j+1)*bsize-1,K); sum -= cnt[j][i]; break; } } if(s == 0){ puts("NIE"); continue; } for(int j=s; j<=e; j++){ lld tmp; if(x[j] <= y[j]){ tmp = get(y[j],i)-get(x[j]-1,i); }else{ tmp = get(y[j],i)+get(M,i)-get(x[j]-1,i); } sum += tmp*z[j]; if(sum >= need[i]){ printf("%d\n",j); break; } } } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 59440 KB | Output is correct |
2 | Correct | 0 ms | 59440 KB | Output is correct |
3 | Correct | 6 ms | 59440 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 0 ms | 59440 KB | Output is correct |
2 | Correct | 3 ms | 59440 KB | Output is correct |
3 | Correct | 6 ms | 59440 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 23 ms | 59704 KB | Output is correct |
2 | Correct | 69 ms | 60100 KB | Output is correct |
3 | Correct | 2599 ms | 59968 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1826 ms | 59836 KB | Output is correct |
2 | Correct | 2039 ms | 59836 KB | Output is correct |
3 | Correct | 99 ms | 60100 KB | Output is correct |
4 | Correct | 186 ms | 59968 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 373 ms | 59836 KB | Output is correct |
2 | Correct | 1283 ms | 60232 KB | Output is correct |
3 | Correct | 96 ms | 59440 KB | Output is correct |
4 | Correct | 2076 ms | 60100 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 189 ms | 59732 KB | Output is correct |
2 | Correct | 1219 ms | 59836 KB | Output is correct |
3 | Correct | 443 ms | 59836 KB | Output is correct |
4 | Correct | 3783 ms | 60232 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 6000 ms | 63136 KB | Execution timed out |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 6000 ms | 63008 KB | Execution timed out |
2 | Halted | 0 ms | 0 KB | - |