| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 931864 |
2024-02-22T13:05:17 Z |
pcc |
Sunčanje (COCI18_suncanje) |
C++14 |
|
950 ms |
154264 KB |
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
const int mxn = 2e5+10;
int N;
struct Q{
int x,l,r,tp;
Q(){x = l = r = tp = 0;}
Q(int xx,int s,int e,int tt){
x = xx,l = s,r = e,tp = tt;
}
bool operator<(Q b)const{
return x == b.x?tp<b.tp:x<b.x;
}
};
bitset<mxn> active;
bitset<mxn> ans;
vector<int> all;
priority_queue<int,vector<int>,less<int>> btag[mxn*4],bseg[mxn*4],stag[mxn*4],sseg[mxn*4];
void modify(int now,int l,int r,int s,int e,int v){
if(l>=s&&e>=r){
while(!btag[now].empty()&&!active[btag[now].top()])btag[now].pop();
while(!bseg[now].empty()&&!active[bseg[now].top()])bseg[now].pop();
int big = 0;
if(!btag[now].empty())big = max(big,btag[now].top());if(!bseg[now].empty())big = max(big,bseg[now].top());
if(big>v)ans[v] = false;
while(!stag[now].empty()&&-stag[now].top()<=v){
if(active[-stag[now].top()])ans[-stag[now].top()] = false;
stag[now].pop();
}
while(!sseg[now].empty()&&-sseg[now].top()<=v){
if(active[-sseg[now].top()])ans[-sseg[now].top()] = false;
sseg[now].pop();
}
sseg[now].push(-v);stag[now].push(-v);btag[now].push(v);bseg[now].push(v);
return;
}
int mid = (l+r)>>1;
if(mid>=s)modify(now*2+1,l,mid,s,e,v);
if(mid<e)modify(now*2+2,mid+1,r,s,e,v);
while(!btag[now].empty()&&!active[btag[now].top()])btag[now].pop();
if(!btag[now].empty()&&btag[now].top()>v)ans[v] = false;
while(!stag[now].empty()&&-stag[now].top()<=v){
if(active[-stag[now].top()])ans[-stag[now].top()] = false;
stag[now].pop();
}
//cout<<now<<":"<<l<<' '<<r<<' '<<s<<' '<<e<<' '<<v<<endl;
bseg[now].push(v);
sseg[now].push(-v);
return;
}
vector<Q> op;
int main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>N;
for(int i = 1;i<=N;i++){
int sx,sy,ex,ey;
cin>>sx>>sy>>ex>>ey;
ex = sx+ex;
ey = sy+ey-1;
op.push_back(Q(sx,sy,ey,i));
op.push_back(Q(ex,sy,ey,-i));
all.push_back(sy);
all.push_back(ey);
}
sort(op.begin(),op.end());
sort(all.begin(),all.end());all.resize(unique(all.begin(),all.end())-all.begin());
ans.set();
for(auto &i:op){
i.l = lower_bound(all.begin(),all.end(),i.l)-all.begin();
i.r = lower_bound(all.begin(),all.end(),i.r)-all.begin();
}
for(auto &i:op){
//cout<<"OP:"<<i.x<<' '<<i.l<<' '<<i.r<<' '<<i.tp<<endl;
if(i.tp<0){
active[-i.tp] = false;
continue;
}
modify(0,0,all.size(),i.l,i.r,i.tp);
active[i.tp] = true;
}
for(int i =1;i<=N;i++){
cout<<(ans[i]?"DA\n":"NE\n");
}
return 0;
}
Compilation message
suncanje.cpp: In function 'void modify(int, int, int, int, int, int)':
suncanje.cpp:36:3: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
36 | if(!btag[now].empty())big = max(big,btag[now].top());if(!bseg[now].empty())big = max(big,bseg[now].top());
| ^~
suncanje.cpp:36:56: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
36 | if(!btag[now].empty())big = max(big,btag[now].top());if(!bseg[now].empty())big = max(big,bseg[now].top());
| ^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
48 ms |
102920 KB |
Output is correct |
| 2 |
Correct |
52 ms |
104172 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
82 ms |
107280 KB |
Output is correct |
| 2 |
Correct |
291 ms |
124164 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
143 ms |
112476 KB |
Output is correct |
| 2 |
Correct |
385 ms |
129228 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
211 ms |
117516 KB |
Output is correct |
| 2 |
Correct |
294 ms |
125184 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
355 ms |
126720 KB |
Output is correct |
| 2 |
Correct |
406 ms |
131524 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
380 ms |
128260 KB |
Output is correct |
| 2 |
Correct |
382 ms |
130100 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
338 ms |
126340 KB |
Output is correct |
| 2 |
Correct |
542 ms |
137484 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
543 ms |
137528 KB |
Output is correct |
| 2 |
Correct |
406 ms |
129588 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
668 ms |
143780 KB |
Output is correct |
| 2 |
Correct |
617 ms |
144636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
950 ms |
154264 KB |
Output is correct |
| 2 |
Correct |
795 ms |
154108 KB |
Output is correct |
