| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 435284 | Cross_Ratio | Distributing Candies (IOI21_candies) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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[] distribute_candies(int[] c, int[] l, int[] r, int[] v) {
int N = c.size();
int Q = l.size();
int i;
for(i=0;i<N;i++) {
seg[i+MAX/2] = Node(c[i],0,c[i]);
}
cons();
for(i=0;i<Q;i++) {
if(v[i] >= 0) {
add1(l[i]-1,r[i],v[i],1,0,MAX/2);
}
else {
add2(l[i]-1,r[i],-v[i],1,0,MAX/2);
}
}
propall();
int ans[N];
for(i=0;i<N;i++) {
ans[i] = seg[i+MAX/2].mare;
}
return ans;
}