QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#48065#2559. Endless RoadPure_FuriesWA 141ms161572kbC++237.6kb2022-09-11 14:56:272022-09-11 14:56:30

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-09-11 14:56:30]
  • 评测
  • 测评结果：WA
  • 用时：141ms
  • 内存：161572kb
查看
  • [2022-09-11 14:56:27]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
int n,l[250003],r[250003];
namespace seg1{
	int dat[1048576],tag[1048576],val[1048576];
	void pushdown(int k){
		if(tag[k]){
			tag[k<<1]=tag[k];
			dat[k<<1]=0;
			tag[k<<1|1]=tag[k];
			dat[k<<1|1]=0; 
		}
	}
	void pushup(int k){
		dat[k]=dat[k<<1]+dat[k<<1|1];
	}
	void modify(int l,int r,int _l,int _r,int k){
		if(_l<=l&&r<=_r){
			dat[k]=0;
			tag[k]=1;
			return;
		}
		if(l>_r||r<_l)return;
		pushdown(k);
		modify(l,l+r>>1,_l,_r,k<<1);
		modify(l+r+1>>1,r,_l,_r,k<<1|1);
		pushup(k);
	}
	int query(int l,int r,int _l,int _r,int k){
		if(_l<=l&&r<=_r)
			return dat[k];
		if(l>_r||r<_l)
			return 0;
		pushdown(k);
		int ret=query(l,l+r>>1,_l,_r,k<<1)+query(l+r+1>>1,r,_l,_r,k<<1|1);
		pushup(k); 
		return ret;
	}
	map<int,int>mp;
	deque<int>v;
	void build(int k,int l,int r){
		dat[k]=v[r+1]-v[l];
		if(l==r)return;
		build(k<<1,l,l+r>>1);
		build(k<<1|1,l+r+1>>1,r);
	}
	void init(){
		for(int i=0;i<n;i++)
			v.push_back(l[i]),
			v.push_back(r[i]);
		sort(v.begin(),v.end());
		v.erase(unique(v.begin(),v.end()),v.end());
		while(v.size()<=524288)
			v.push_back(v.back()+1);
		for(int i=0;i<v.size();i++)
			mp[v[i]]=i;
		build(1,0,524287);
	}
}
int nxt[2][2][8000003],N;
namespace seg2{
	pair<int,int>dat[8000003];
	void pushup(int k){
		dat[k].first=998244353;
		if(nxt[0][0][k]!=-1)dat[k]=min(dat[nxt[0][0][k]],dat[k]);
		if(nxt[0][1][k]!=-1)dat[k]=min(dat[nxt[0][1][k]],dat[k]);
		if(nxt[1][0][k]!=-1)dat[k]=min(dat[nxt[1][0][k]],dat[k]);
		if(nxt[1][1][k]!=-1)dat[k]=min(dat[nxt[1][1][k]],dat[k]);
	}
	int change(int _lx,int _rx,int _ly,int _ry,int x,int y,int k,pair<int,int>val){
		if(k==-1)
			k=++N;
		if(_lx==_rx&&_ly==_ry){
			dat[k]=val;
			return k;
		}
		if(x<=(_lx+_rx>>1)&&y<=(_ly+_ry>>1))nxt[0][0][k]=change(_lx,_lx+_rx>>1,_ly,_ly+_ry>>1,x,y,nxt[0][0][k],val);
		if(x<=(_lx+_rx>>1)&&y>(_ly+_ry>>1))nxt[0][1][k]=change(_lx,_lx+_rx>>1,_ly+_ry+1>>1,_ry,x,y,nxt[0][1][k],val);
		if(x>(_lx+_rx>>1)&&y<=(_ly+_ry>>1))nxt[1][0][k]=change(_lx+_rx+1>>1,_rx,_ly,_ly+_ry>>1,x,y,nxt[1][0][k],val);
		if(x>(_lx+_rx>>1)&&y>(_ly+_ry>>1))nxt[1][1][k]=change(_lx+_rx+1>>1,_rx,_ly+_ry+1>>1,_ry,x,y,nxt[1][1][k],val);
		pushup(k);
		return k;
	}
	pair<int,int>query(int _lx,int _rx,int _ly,int _ry,int lx,int rx,int ly,int ry,int k){
		if(k==-1||lx>_rx||rx<_lx||ly>_ry||ry<_ly)return {998244353,-1};
		if(lx<=_lx&&_rx<=rx&&ly<=_ly&&_ry<=ry)return dat[k];
		pair<int,int>ret={998244353,-1};
		ret=min(ret,query(_lx,_lx+_rx>>1,_ly,_ly+_ry>>1,lx,rx,ly,ry,nxt[0][0][k]));
		ret=min(ret,query(_lx,_lx+_rx>>1,_ly+_ry+1>>1,_ry,lx,rx,ly,ry,nxt[0][1][k]));
		ret=min(ret,query(_lx+_rx+1>>1,_rx,_ly,_ly+_ry>>1,lx,rx,ly,ry,nxt[1][0][k]));
		ret=min(ret,query(_lx+_rx+1>>1,_rx,_ly+_ry+1>>1,_ry,lx,rx,ly,ry,nxt[1][1][k]));
		return ret;
	}
}
namespace seg3{
	pair<int,int>dat[8000003];
	void pushup(int k){
		dat[k].first=998244353;
		if(nxt[0][0][k]!=-1)dat[k]=min(dat[nxt[0][0][k]],dat[k]);
		if(nxt[0][1][k]!=-1)dat[k]=min(dat[nxt[0][1][k]],dat[k]);
		if(nxt[1][0][k]!=-1)dat[k]=min(dat[nxt[1][0][k]],dat[k]);
		if(nxt[1][1][k]!=-1)dat[k]=min(dat[nxt[1][1][k]],dat[k]);
	}
	int change(int _lx,int _rx,int _ly,int _ry,int x,int y,int k,pair<int,int>val){
		if(k==-1)
			k=++N;
		if(_lx==_rx&&_ly==_ry){
			dat[k]=val;
			return k;
		}
		if(x<=(_lx+_rx>>1)&&y<=(_ly+_ry>>1))nxt[0][0][k]=change(_lx,_lx+_rx>>1,_ly,_ly+_ry>>1,x,y,nxt[0][0][k],val);
		if(x<=(_lx+_rx>>1)&&y>(_ly+_ry>>1))nxt[0][1][k]=change(_lx,_lx+_rx>>1,_ly+_ry+1>>1,_ry,x,y,nxt[0][1][k],val);
		if(x>(_lx+_rx>>1)&&y<=(_ly+_ry>>1))nxt[1][0][k]=change(_lx+_rx+1>>1,_rx,_ly,_ly+_ry>>1,x,y,nxt[1][0][k],val);
		if(x>(_lx+_rx>>1)&&y>(_ly+_ry>>1))nxt[1][1][k]=change(_lx+_rx+1>>1,_rx,_ly+_ry+1>>1,_ry,x,y,nxt[1][1][k],val);
		pushup(k);
		return k;
	}
	pair<int,int>query(int _lx,int _rx,int _ly,int _ry,int lx,int rx,int ly,int ry,int k){
		if(k==-1||lx>_rx||rx<_lx||ly>_ry||ry<_ly)return {998244353,-1};
		if(lx<=_lx&&_rx<=rx&&ly<=_ly&&_ry<=ry)return dat[k];
		pair<int,int>ret={998244353,-1};
		ret=min(ret,query(_lx,_lx+_rx>>1,_ly,_ly+_ry>>1,lx,rx,ly,ry,nxt[0][0][k]));
		ret=min(ret,query(_lx,_lx+_rx>>1,_ly+_ry+1>>1,_ry,lx,rx,ly,ry,nxt[0][1][k]));
		ret=min(ret,query(_lx+_rx+1>>1,_rx,_ly,_ly+_ry>>1,lx,rx,ly,ry,nxt[1][0][k]));
		ret=min(ret,query(_lx+_rx+1>>1,_rx,_ly+_ry+1>>1,_ry,lx,rx,ly,ry,nxt[1][1][k]));
		return ret;
	}
}
namespace seg4{
	pair<int,int>dat[8000003];
	int lzy[8000003]; 
	void pushup(int k){
		dat[k].first=998244353;
		if(nxt[0][0][k]!=-1)dat[k]=min(dat[nxt[0][0][k]],dat[k]);
		if(nxt[0][1][k]!=-1)dat[k]=min(dat[nxt[0][1][k]],dat[k]);
		if(nxt[1][0][k]!=-1)dat[k]=min(dat[nxt[1][0][k]],dat[k]);
		if(nxt[1][1][k]!=-1)dat[k]=min(dat[nxt[1][1][k]],dat[k]);
	}
	void pushdown(int k){
		if(nxt[0][0][k]!=-1)lzy[nxt[0][0][k]]+=lzy[k],dat[nxt[0][0][k]].first+=lzy[k];
		if(nxt[0][1][k]!=-1)lzy[nxt[0][1][k]]+=lzy[k],dat[nxt[0][1][k]].first+=lzy[k];
		if(nxt[1][0][k]!=-1)lzy[nxt[1][0][k]]+=lzy[k],dat[nxt[1][0][k]].first+=lzy[k];
		if(nxt[1][1][k]!=-1)lzy[nxt[1][1][k]]+=lzy[k],dat[nxt[1][1][k]].first+=lzy[k];
		lzy[k]=0;
	}
	int change(int _lx,int _rx,int _ly,int _ry,int x,int y,int k,pair<int,int>val){
		if(k==-1)
			k=++N;
		if(_lx==_rx&&_ly==_ry){
			dat[k]=val;
			return k;
		}
		pushdown(k);
		if(x<=(_lx+_rx>>1)&&y<=(_ly+_ry>>1))nxt[0][0][k]=change(_lx,_lx+_rx>>1,_ly,_ly+_ry>>1,x,y,nxt[0][0][k],val);
		if(x<=(_lx+_rx>>1)&&y>(_ly+_ry>>1))nxt[0][1][k]=change(_lx,_lx+_rx>>1,_ly+_ry+1>>1,_ry,x,y,nxt[0][1][k],val);
		if(x>(_lx+_rx>>1)&&y<=(_ly+_ry>>1))nxt[1][0][k]=change(_lx+_rx+1>>1,_rx,_ly,_ly+_ry>>1,x,y,nxt[1][0][k],val);
		if(x>(_lx+_rx>>1)&&y>(_ly+_ry>>1))nxt[1][1][k]=change(_lx+_rx+1>>1,_rx,_ly+_ry+1>>1,_ry,x,y,nxt[1][1][k],val);
		pushup(k);
		return k;
	}
	void add(int _lx,int _rx,int _ly,int _ry,int lx,int ly,int rx,int ry,int k,int val){
		if(k==-1||lx>_rx||rx<_lx||ly>_ry||ry<_ly)return;
		if(lx<=_lx&&_rx<=rx&&ly<=_ly&&_ry<=ry){lzy[k]+=val;dat[k].first+=val;return;}
		pushdown(k);
		add(_lx,_lx+_rx>>1,_ly,_ly+_ry>>1,lx,ly,rx,ry,nxt[0][0][k],val);
		add(_lx,_lx+_rx>>1,_ly+_ry+1>>1,_ry,lx,ly,rx,ry,nxt[0][1][k],val);
		add(_lx+_rx+1>>1,_rx,_ly,_ly+_ry>>1,lx,ly,rx,ry,nxt[1][0][k],val);
		add(_lx+_rx+1>>1,_rx,_ly+_ry+1>>1,_ry,lx,ly,rx,ry,nxt[1][1][k],val);
		pushup(k);
		return;
	}
}
int main(){
	memset(nxt,-1,sizeof(nxt));
	scanf("%d",&n);
	for(int i=0;i<n;i++)
		scanf("%d%d",l+i,r+i);
	seg1::init();
	for(int i=0;i<n;i++){
		seg2::change(0,1073741823,0,1073741823,l[i],r[i],0,{r[i],i});
		seg3::change(0,1073741823,0,1073741823,l[i],r[i],0,{-l[i],i});
		seg4::change(0,1073741823,0,1073741823,l[i],r[i],0,{r[i]-l[i],i});
	}
	for(int i=0;i<n;i++){
		int nw=seg4::dat[0].second;
		printf("%d ",nw+1);
		int del=seg1::query(0,524287,seg1::mp[l[nw]],seg1::mp[r[nw]]-1,1);
		seg1::modify(0,524287,seg1::mp[l[nw]],seg1::mp[r[nw]]-1,1);
		seg2::change(0,1073741823,0,1073741823,l[nw],r[nw],0,{998244353,-1});
		int newl=seg2::query(0,1073741823,0,1073741823,l[nw],r[nw],0,1073741823,0).second;
		seg3::change(0,1073741823,0,1073741823,l[nw],r[nw],0,{998244353,-1});
		int newr=seg3::query(0,1073741823,0,1073741823,0,1073741823,l[nw],r[nw],0).second;
		seg4::change(0,1073741823,0,1073741823,l[nw],r[nw],0,{998244353,-1});
		seg4::add(0,1073741823,0,1073741823,0,l[nw],r[nw],1073741823,0,-del);
		if(newl!=-1){
			int vall=seg1::query(0,524287,seg1::mp[l[newl]],seg1::mp[r[newl]]-1,1);
			seg4::change(0,1073741823,0,1073741823,l[newl],r[newl],0,{vall,newl});
		}
		if(newr!=-1){
			int valr=seg1::query(0,524287,seg1::mp[l[newr]],seg1::mp[r[newr]]-1,1);
			seg4::change(0,1073741823,0,1073741823,l[newr],r[newr],0,{valr,newr});
		}
	}
}
源文件, 语言: C++23

詳細信息

Test #1:

score: 0
Wrong Answer
time: 141ms
memory: 161572kb

input:

6
1 2
2 3
3 4
4 5
1 3
3 5

output:

1 2 5 3 6 4

result:

wrong answer 5th words differ - expected: '4', found: '6'
English 繁體中文 简体中文

伺服器時間: 2025-01-20 19:12:22 | 開源專案