# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
41238 | 2018-02-15T05:01:11 Z | wzy | Meteors (POI11_met) | C++14 | 6000 ms | 23412 KB |
#include <bits/stdc++.h> #define F first #define S second using namespace std; int ans[300005],n , m , qt[300005] , k; vector<int> o[300005]; vector<pair< pair<int,int> , int > > querys; long long bit[300005]; void upd(int x , int vl){ for(int i = x; i < 300005 ; i+= (i&-i)){ bit[i] += vl; } } int qr(int x){ if(x == 0) return 0; int s = 0; for(int i = x ; i > 0 ; i-=(i&-i)){ if(s >= (int) 1e17){ if(bit[i] >= (int) 1e17) continue; else s += bit[i]; } else if(s <= -((int) 1e17)){ if(bit[i] <= -((int) 1e17)) continue; else s+= bit[i]; } else s+= bit[i]; } return s; } void update(int x , int y, int vl){ upd(x, vl); upd(y+1, -vl); } int query(int x){ return qr(x); } void solve(int l , int r , const vector<int> & opt){ int mid = (l+r)/2; memset(bit, 0 , sizeof bit); for(int i = 0 ; i < mid ; i++){ pair< pair<int,int> , int> info = querys[i]; if(info.F.F > info.F.S){ update(info.F.F , m , info.S); update(1, info.F.S , info.S); } else{ update(info.F.F , info.F.S , info.S); } } vector<int> leftc , rightc; for(int j = 0 ; j < opt.size() ; j++){ int i = opt[j]; int sj = 0; for(int w = 0 ; w < o[i].size(); w++){ int c = o[i][w]; sj += query(c); if(sj >= qt[i]) break; } if(sj >= qt[i]) leftc.push_back(i); else rightc.push_back(i); } if(l == r){ for(int i = 0 ; i < leftc.size();i++) ans[leftc[i]] = l; for(int i = 0 ; i < rightc.size();i++) ans[rightc[i]] = -1; leftc.clear() , rightc.clear(); return; } else{ if(leftc.size()){ solve(l , mid , leftc); leftc.clear(); } if(rightc.size()){ solve(mid + 1 , r , rightc); rightc.clear(); } } } int main(){ scanf("%d%d" , &n , &m); vector<int> candidatos; for(int i = 1 ; i <= m;i++){ int x; scanf("%d" , &x); o[x].push_back(i); } for(int i = 1 ; i<= n ;i++){ scanf("%d" , &qt[i]); candidatos.push_back(i); } scanf("%d" , &k); for(int i = 0 ; i < k ;i ++){ int l , r ,v; scanf("%d%d%d" , &l , &r , &v); querys.push_back(pair<pair<int,int> , int>(pair<int,int>(l , r) , v)); } solve(1, k , candidatos); for(int i = 1 ; i <= n; i++){ if(ans[i] == -1) puts("NIE"); else printf("%d\n" , ans[i]); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 67 ms | 9720 KB | Output is correct |
2 | Correct | 34 ms | 9952 KB | Output is correct |
3 | Correct | 159 ms | 10004 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 15 ms | 10076 KB | Output is correct |
2 | Correct | 15 ms | 10076 KB | Output is correct |
3 | Correct | 232 ms | 10148 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 147 ms | 11340 KB | Output is correct |
2 | Correct | 3617 ms | 13312 KB | Output is correct |
3 | Execution timed out | 6017 ms | 13312 KB | Time limit exceeded |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 6098 ms | 13312 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 6045 ms | 13312 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2663 ms | 13312 KB | Output is correct |
2 | Execution timed out | 6018 ms | 13312 KB | Time limit exceeded |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 6035 ms | 23412 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Execution timed out | 6025 ms | 23412 KB | Time limit exceeded |
2 | Halted | 0 ms | 0 KB | - |