| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 435287 | Cross_Ratio | Distributing Candies (IOI21_candies) | C++17 | 0 ms | 0 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>
using namespace std;
const int MAX = 1<<19;
const int INF = 2*1e9;
struct Node {
int mapl; // how many minimum plus remain?
int mipl;
int mare; // how many minimum remain?
int mire;
int p;
bool full;
bool zero;
int mac;
int mic;
Node() : mapl(0),mipl(INF),mare(0),mire(INF),p(0),full(false),zero(false),mac(-INF),mic(INF){}
Node(int p1, int r1,int c1) : mapl(p1),mipl(p1),mare(r1),mire(r1),p(0),full(false),zero(false),mac(c1),mic(c1){}
};
Node f(Node x, Node y) {
Node s;
s.mapl = max(x.mapl, y.mapl);
s.mipl = min(x.mipl, y.mipl);
s.mare = max(x.mare, y.mare);
s.mire = min(x.mire, y.mire);
s.mac = max(x.mac,y.mac);
s.mic = min(x.mic,y.mic);
return s;
}
Node seg[MAX];
void cons() {
int i;
for(i=MAX/2-1;i>0;i--) {
seg[i] = f(seg[2*i],seg[2*i+1]);
}
}
void prop(int n, int ns, int ne) {
if(seg[n].p == 0&&!seg[n].full&&!seg[n].zero) return;
seg[n].mare += seg[n].p;
seg[n].mire += seg[n].p;
seg[n].mapl -= seg[n].p;
seg[n].mipl -= seg[n].p;
if(seg[n].full) {
seg[n].mare = seg[n].mac;
seg[n].mire = seg[n].mic;
seg[n].mapl = 0;
seg[n].mipl = 0;
}
if(seg[n].zero) {
seg[n].mare = 0;
seg[n].mire = 0;
seg[n].mapl = seg[n].mac;
seg[n].mipl = seg[n].mic;
}
if(n >= MAX/2) {
seg[n].p = 0;
seg[n].zero = false;
seg[n].full = false;
return;
}
else {
int i;
for(i=2*n;i<=2*n+1;i++) {
seg[i].p += seg[n].p;
if(seg[i].zero) seg[n].zero = true;
if(seg[i].full) seg[n].full = true;
}
seg[n].p = 0;
seg[n].zero = false;
seg[n].full = false;
return;
}
}
void add1(int s, int e, int a, int n, int ns, int ne) {
prop(n,ns,ne);
if(e<=ns||ne<=s) return;
if(s<=ns&&ne<=e&&seg[n].mipl>=a) {
seg[n].p += a;
prop(n,ns,ne);
return;
}
if(s<=ns&&ne<=e&&seg[n].mapl<=a) {
seg[n].full = true;
//seg[n].p += seg[n].mapl;
prop(n,ns,ne);
return;
}
int mid = (ns + ne) / 2;
add1(s,e,a,2*n,ns,mid);
add1(s,e,a,2*n+1,mid,ne);
if(n<MAX/2) seg[n] = f(seg[2*n],seg[2*n+1]);
}
void add2(int s, int e, int m, int n, int ns, int ne) {
prop(n,ns,ne);
if(e<=ns||ne<=s) return;
if(s<=ns&&ne<=e&&seg[n].mire>=m) {
seg[n].p -= m;
prop(n,ns,ne);
return;
}
if(s<=ns&&ne<=e&&seg[n].mare<=m) {
seg[n].zero = true;
//seg[n].p -= seg[n].mare;
prop(n,ns,ne);
return;
}
int mid = (ns + ne) / 2;
add1(s,e,m,2*n,ns,mid);
add1(s,e,m,2*n+1,mid,ne);
if(n<MAX/2) seg[n] = f(seg[2*n],seg[2*n+1]);
}
void propall() {
int i;
for(i=1;i<MAX;i++) prop(1,1,1);
}
int main() {
cin.sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int N;
cin >> N;
int i;
int a,b,c;
for(i=0;i<N;i++) {
cin >> a;
seg[i+MAX/2] = Node(a,0,a);
}
int Q;
cons();
cin >> Q;
for(i=0;i<Q;i++) {
cin >> a >> b >> c;
if(c >= 0) {
add1(a-1,b,c,1,0,MAX/2);
}
if(c<0) {
add2(a-1,b,-c,1,0,MAX/2);
}
}
propall();
for(i=0;i<N;i++) {
cout << seg[i+MAX/2].mare << ' ';
}
}