oj.uz

답안 #931864

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
931864 2024-02-22T13:05:17 Z pcc Sunčanje (COCI18_suncanje) C++14
130 / 130
 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());
      |                                                        ^~

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 48 ms 102920 KB Output is correct
2 Correct 52 ms 104172 KB Output is correct

Subtask #2
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 107280 KB Output is correct
2 Correct 291 ms 124164 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 143 ms 112476 KB Output is correct
2 Correct 385 ms 129228 KB Output is correct

Subtask #4
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 211 ms 117516 KB Output is correct
2 Correct 294 ms 125184 KB Output is correct

Subtask #5
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 355 ms 126720 KB Output is correct
2 Correct 406 ms 131524 KB Output is correct

Subtask #6
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 380 ms 128260 KB Output is correct
2 Correct 382 ms 130100 KB Output is correct

Subtask #7
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 338 ms 126340 KB Output is correct
2 Correct 542 ms 137484 KB Output is correct

Subtask #8
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 543 ms 137528 KB Output is correct
2 Correct 406 ms 129588 KB Output is correct

Subtask #9
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 668 ms 143780 KB Output is correct
2 Correct 617 ms 144636 KB Output is correct

Subtask #10
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 950 ms 154264 KB Output is correct
2 Correct 795 ms 154108 KB Output is correct