oj.uz

Submission #931861

# Submission time Handle Problem Language Result Execution time Memory
931861 2024-02-22T13:00:47 Z pcc Sunčanje (COCI18_suncanje) C++14
0 / 130
 885 ms 163488 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>,greater<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());
      |                                                        ^~

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 54 ms 103252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 86 ms 108024 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 142 ms 113920 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 197 ms 119320 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 349 ms 129836 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 364 ms 131872 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 328 ms 128700 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 529 ms 141048 KB Output is correct
2 Incorrect 386 ms 133632 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 604 ms 147632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 885 ms 163488 KB Output isn't correct
2 Halted 0 ms 0 KB -