oj.uz

Submission #890347

# Submission time Handle Problem Language Result Execution time Memory
890347 2023-12-21T04:08:11 Z pcc Sunčanje (COCI18_suncanje) C++14
39 / 130
 884 ms 262144 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>
#define mid ((l+r)>>1)


const int mxn = 2e5+10;
vector<int> all;
priority_queue<int,vector<int>,greater<int>> mn[mxn*4];
priority_queue<int,vector<int>,less<int>> mx[mxn*4];
vector<int> mxtag[mxn*4];
vector<int> mntag[mxn*4];
bitset<mxn> out;

struct Q{
	int tp,l,r,id,y;
	Q(){}
	bool operator<(const Q&b)const{
		return y == b.y?tp<b.tp:y<b.y;
	}
};

vector<Q> req;
int n;
bitset<mxn> ans;

void korosu(int now,int id){
	while(!mn[now].empty()&&(out[mn[now].top()]||mn[now].top()<id)){
		if(!out[mn[now].top()])ans[mn[now].top()] = false;
		mn[now].pop();
	}
	return;
}
void korosareru(int now,int id){
	while(!mx[now].empty()&&out[mx[now].top()])mx[now].pop();
	//cout<<"korosareru:"<<now<<":"<<id<<' '<<(mx[now].empty()?0:mx[now].top())<<endl;
	if(!mx[now].empty()&&mx[now].top()>id)ans[id] = false;
	return;
}

void push(int now,int l,int r){
	for(auto &i:mxtag[now]){
		if(out[i])continue;
		mx[now].push(i);
	}
	for(auto &i:mntag[now]){
		if(out[i])continue;
		mn[now].push(i);
	}
	if(l != r){
		for(auto &i:mxtag[now]){
			if(out[i])continue;
			mxtag[now*2+1].push_back(i);
			mxtag[now*2+2].push_back(i);
		}
		for(auto &i:mntag[now]){
			if(out[i])continue;
			mntag[now*2+1].push_back(i);
			mntag[now*2+2].push_back(i);
		}
	}
	mntag[now].clear();
	mxtag[now].clear();
	return;
}

void add(int now,int l,int r,int s,int e,int id){
	mn[now].push(id);
	mx[now].push(id);
	//cout<<l<<' '<<r<<" mxtag:";for(auto &j:mxtag[now])cout<<j<<',';cout<<endl;
	push(now,l,r);
	if(l>=s&&e>=r){
		korosareru(now,id);
		korosu(now,id);
		mxtag[now].push_back(id);
		mntag[now].push_back(id);
		//cout<<now<<":"<<l<<' '<<r<<":"<<id<<endl;
		return;
	}
	if(mid>=s)add(now*2+1,l,mid,s,e,id);
	if(mid<e)add(now*2+2,mid+1,r,s,e,id);
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n;
	ans.set();
	for(int i = 1;i<=n;i++){
		int x,y,w,h;
		cin>>x>>y>>w>>h;
		Q tmp;
		tmp.id = i;
		tmp.l = x,tmp.r = x+w-1;
		tmp.y = y;tmp.tp = 1;
		all.push_back(tmp.l);all.push_back(tmp.r);
		req.push_back(tmp);
		tmp.y += h;tmp.tp = 0;
		req.push_back(tmp);
	}
	sort(all.begin(),all.end());
	all.resize(unique(all.begin(),all.end())-all.begin());
	for(auto &i:req){
		i.l = lower_bound(all.begin(),all.end(),i.l)-all.begin();
		i.r = lower_bound(all.begin(),all.end(),i.r)-all.begin();
	}
	sort(req.begin(),req.end());
	/*
	for(auto &i:all)cout<<i<<',';cout<<endl<<endl;
	for(auto &i:req){
		cout<<i.y<<','<<i.id<<' '<<i.tp<<":"<<i.l<<' '<<i.r<<endl;
	}
   */
	for(auto &i:req){
		//cout<<i.tp<<' '<<i.id<<endl;
		if(i.tp)add(0,0,all.size(),i.l,i.r,i.id);
		else out[i.id] = true;
		//cout<<endl;
	}

	for(int i = 1;i<=n;i++)cout<<(ans[i]?"DA\n":"NE\n");
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 91820 KB Output is correct
2 Correct 61 ms 92704 KB Output is correct

Subtask #2
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 198 ms 118116 KB Output is correct
2 Correct 404 ms 124012 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 627 ms 199036 KB Output is correct
2 Correct 429 ms 122208 KB Output is correct

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 764 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 884 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 748 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 436 ms 116432 KB Output is correct
2 Runtime error 554 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #8
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 557 ms 127424 KB Output is correct
2 Runtime error 663 ms 262144 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #9
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 848 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #10
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 784 ms 262144 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -