제출 #1231023

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1231023		nhnguyen14	Sunčanje (COCI18_suncanje)	C++20	0 / 130	434 ms	139580 KiB

suncanje

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N=(int)2e5;
const int INF=(int)1e9;
	bool active[N+2]={},ans[N+2]={};
	int x[N+2],y[N+2],a[N+2],b[N+2];
	int lef_y[N+2],rig_y[N+2];
	int n;
	vector<int>valuex,valuey;
	vector<int>del[N+2];
	vector<int>add[N+2];
	
struct Node{
	priority_queue<int,vector<int>,greater<int>> bao[2];
	priority_queue<int,vector<int>,less<int>>conlai[2];
	int Get_max(int x){
		while (conlai[x].size() && !active[conlai[x].top()]) conlai[x].pop();
		return (conlai[x].size() ? conlai[x].top() : -1);
	}
	void modify(int cur_ID,int x){
		while (bao[x].size() && (bao[x].top()<cur_ID || !active[bao[x].top()] || ans[bao[x].top()])) {
			if (active[bao[x].top()]) ans[bao[x].top()]=true;
			bao[x].pop();
		}
		return;
	}
};
Node st[N*4+2];
	
	void upd(int id,int l,int r,int u,int v,int cur_ID){
		if (l>v||r<u) return;
		if (u<=l && r<=v){
			if (st[id].Get_max(1)>cur_ID) ans[cur_ID]=true;
			st[id].modify(cur_ID,1);
			if (ans[cur_ID]==0){
				for(int j=0;j<2;++j) st[id].conlai[j].push(cur_ID);
			}
			for(int j=0;j<2;++j) st[id].bao[j].push(cur_ID);
			return;
		}
		int m=(l+r)/2;
		if (st[id].Get_max(0)>cur_ID) ans[cur_ID]=true;
		st[id].modify(cur_ID,0);
		if (ans[cur_ID]==0) st[id].conlai[1].push(cur_ID);
		st[id].bao[1].push(cur_ID);
		upd(id*2,l,m,u,v,cur_ID);
		upd(id*2+1,m+1,r,u,v,cur_ID);
	}

int Find(vector<int>&data,int x){
	return upper_bound(data.begin(),data.end(),x)-data.begin();
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);
	#define task "main"
	if (fopen(task".inp","r")){
		freopen(task".inp","r",stdin);
		freopen(task".out","w",stdout);
	}
		
	cin>>n;
	for(int i=1;i<=n;++i) {
		cin>>x[i]>>y[i];
		cin>>a[i]>>b[i];
		valuex.push_back(x[i]);
		valuex.push_back(x[i]+a[i]-1);
		valuey.push_back(y[i]);
		valuey.push_back(y[i]+b[i]-1);
	}
	sort(valuex.begin(),valuex.end()); 
	valuex.resize(unique(valuex.begin(),valuex.end())-valuex.begin());
	sort(valuey.begin(),valuey.end());
	valuey.resize(unique(valuey.begin(),valuey.end())-valuey.begin());
	int nen_y=valuey.size();
	int nen_x=valuex.size();
	for(int i=1;i<=n;++i){
		lef_y[i]=Find(valuey,y[i]);
		rig_y[i]=Find(valuey,y[i]+b[i]-1);
		int lef_x=Find(valuex,x[i]);
		int rig_x=Find(valuex,x[i]+a[i]-1);
		add[lef_x].push_back(i);
		del[rig_x].push_back(i);
	}
	for(int i=1;i<=nen_x;++i){
		for(auto&x:add[i]) {
			active[x]=true;
			upd(1,1,n,lef_y[x],rig_y[x],x);
		}
		for(auto&x:del[i]) active[x]=false;
	}
	for(int i=1;i<=n;++i) cout<<(ans[i]?"NE":"DA")<<'\n';
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

suncanje.cpp: In function 'int main()':
suncanje.cpp:61:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |                 freopen(task".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
suncanje.cpp:62:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |                 freopen(task".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 13
• Subtask 2: 0 / 13
• Subtask 3: 0 / 13
• Subtask 4: 0 / 13
• Subtask 5: 0 / 13
• Subtask 6: 0 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13
• Subtask 9: 0 / 13
• Subtask 10: 0 / 13