제출 #434173

#제출 시각아이디문제언어결과실행 시간메모리
434173vanicHandcrafted Gift (IOI20_gift)C++14
100 / 100
579 ms24932 KiB
#include "gift.h" #include <iostream> #include <cmath> #include <algorithm> #include <vector> using namespace std; const int maxn=5e5+5; const string s="RB"; const int Log=19, pot=(1<<Log); int t1[pot*2], t2[pot*2]; void update(int x, int val){ t1[x]=t2[x]=val; for(x/=2; x>0; x/=2){ t1[x]=max(t1[x*2], t1[x*2+1]); t2[x]=min(t2[x*2], t2[x*2+1]); } } pair < int, int > query(int L, int D, int x, int l, int d){ if(L>=l && D<=d){ return {t1[x], t2[x]}; } pair < int, int > lijeva={0, 1}, desna={0, 1}; if((L+D)/2>=l){ lijeva=query(L, (L+D)/2, x*2, l, d); } if((L+D)/2+1<=d){ desna=query((L+D)/2+1, D, x*2+1, l, d); } return {max(lijeva.first, desna.first), min(lijeva.second, desna.second)}; } int poz[maxn]; int neg[maxn]; string sol; int construct(int n, int r, vector<int> a, vector<int> b, vector<int> x) { for(int i=0; i<r; i++){ if(x[i]==1){ poz[a[i]]++; neg[b[i]+1]++; } } int sw=0; bool pp=0; for(int i=0; i<n; i++){ sw-=neg[i]; if(!sw){ pp^=1; } sw+=poz[i]; update(i+pot, pp); sol.push_back(s[pp]); } pair < int, int > p; for(int i=0; i<r; i++){ if(x[i]==2){ p=query(0, pot-1, 1, a[i], b[i]); if(p.first==p.second){ return 0; } } } craft(sol); return 1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...