# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
29312 | tlwpdus | Meteors (POI11_met) | C++11 | 3383 ms | 38588 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define s first
#define e second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int n, m, k;
struct query {
int l, r; ll a;
query(){}
query(int l, int r, ll a):l(l),r(r),a(a){}
};
struct idxtree {
ll tree[1050000];
int key = 524288;
void init() {
for (int i=0;i<key*2;i++) tree[i] = 0;
}
void updr(int s, int e, ll val) {
s+=key;e+=key;
while(s<=e) {
if (s&1) tree[s] += val;
if (~e&1) tree[e] += val;
s = (s+1)>>1; e = (e-1)>>1;
}
}
ll getv(int idx) {
ll res = 0;
idx += key;
while(idx>0) {
res += tree[idx];
idx>>=1;
}
return res;
}
void upd(int s, int e, ll val) {
if (s<=e) updr(s,e,val);
else {
updr(s,m-1,val);
updr(0,e,val);
}
}
} it;
int own[300100];
vector<int> lis[300100];
ll p[300100];
query arr[300100];
pii loc[300100];
pii yan[300100];
int res[300100];
void init(int s, int e) {
if (s>e) return;
int m = (s+e)>>1;
yan[m] = pii(s,e);
init(s,m-1); init(m+1,e);
}
void pb() {
int i, j, pp = 0;
for (i=0;i<n;i++) loc[i] = pii((k+1)/2,i);
init(1,k);
while(pp<n) {
bool flag = 1;
it.init();
j = 0;
int cn = n-pp;
for (i=1;i<=k;i++) {
it.upd(arr[i-1].l,arr[i-1].r,arr[i-1].a);
while(j<cn&&loc[j].first==i) {
int v = loc[j].second;
flag = 0;
ll sum = 0;
for (int l : lis[v]) {
sum += it.getv(l);
sum = min(sum,1000000100LL);
}
if (sum>=p[v]) {
if (i==yan[i].s) {
res[v] = i;
loc[j].first = k+10; pp++;
}
else loc[j].first = (yan[i].s+i-1)/2;
}
else {
if (i==yan[i].e) {
res[v] = i+1;
loc[j].first = k+10; pp++;
}
else loc[j].first = (yan[i].e+i+1)/2;
}
j++;
}
}
if (flag) break;
sort(loc,loc+cn);
}
}
int main() {
int i;
scanf("%d%d",&n,&m);
for (i=0;i<m;i++) {
scanf("%d",&own[i]); own[i]--;
lis[own[i]].push_back(i);
}
for (i=0;i<n;i++) scanf("%lld",&p[i]);
scanf("%d",&k);
for (i=0;i<k;i++) {
int l, r; ll a;
scanf("%d%d%lld",&l,&r,&a); l--; r--;
arr[i] = query(l,r,a);
}
pb();
for (i=0;i<n;i++) {
if (res[i]>=k+1) printf("NIE\n");
else printf("%d\n",res[i]);
}
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |