QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#26621#2559. Endless RoadMr_EightWA 7ms39804kbC++146.7kb2022-04-07 20:15:312022-04-29 04:07:20

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-29 04:07:20]
  • 评测
  • 测评结果：WA
  • 用时：7ms
  • 内存：39804kb
查看
  • [2022-04-07 20:15:31]
  • 提交

answer

//#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <cmath>
#include <algorithm>
#include <climits>
#include <functional>
#include <cstring>
#include <string>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <complex>
#include <random>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/priority_queue.hpp>
#define itn int
#define nit int
#define ll long long
#define ms multiset
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define UF(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
#define re register
#define ri re int
#define il inline
#define pii pair<int,int>
#define cp complex<double>
#define vi vector<int>
#define ull unsigned long long
#define mem0(x) memset(x,0,sizeof(x))
#define mem0x3f(x) memset(x,0x3f,sizeof(x))
using namespace std;
//using namespace __gnu_pbds;
const double Pi=acos(-1);
namespace fastIO {
	template<class T>
	inline void read(T &x) {
		x=0;
		bool fu=0;
		char ch=0;
		while(ch>'9'||ch<'0') {
			ch=getchar();
			if(ch=='-')fu=1;
		}
		while(ch<='9'&&ch>='0') x=(x*10-48+ch),ch=getchar();
		if(fu)x=-x;
	}
	inline int read() {
		int x=0;
		bool fu=0;
		char ch=0;
		while(ch>'9'||ch<'0') {
			ch=getchar();
			if(ch=='-')fu=1;
		}
		while(ch<='9'&&ch>='0') x=(x*10-48+ch),ch=getchar();
		return fu?-x:x;
	}
	template<class T,class... Args>
	inline void read(T& t,Args&... args) {
		read(t);
		read(args...);
	}
	char _n_u_m_[40];
	template<class T>
	inline void write(T x) {
		if(x==0){
			putchar('0');
			return;
		}
		T tmp = x > 0 ? x : -x ;
		if( x < 0 ) putchar('-') ;
		register int cnt = 0 ;
		while( tmp > 0 ) {
			_n_u_m_[ cnt ++ ] = tmp % 10 + '0' ;
			tmp /= 10 ;
		}
		while( cnt > 0 ) putchar(_n_u_m_[ -- cnt ]) ;
	}
	template<class T>
	inline void write(T x ,char ch) {
		write(x);
		putchar(ch);
	}
}
using namespace fastIO;
namespace G{
	int l[500002],r[500002],tl[500002],tr[500002];
}
using namespace G;
int n;
int p[500002],m,qwq[500002];
pii temp[500002];
#define mid ((l+r)>>1)
namespace B{
	int c[500002];
	inline void add(int pos,int v){
		while(pos<=m){
			c[pos]+=v;
			pos+=(-pos&pos);
		}
	}
	inline int query(int pos){
		int rt=0;
		while(pos){
			rt+=c[pos];
			pos-=(-pos&pos);
		}
		return rt;
	}
};
inline void update(int pos);
namespace S{
	pii mmin[2000002];
	inline void build(int pos,int l,int r){
		if(l==r)mmin[pos]=temp[l];
		else{
			build(pos<<1,l,mid);build(pos<<1|1,mid+1,r);
			mmin[pos]=min(mmin[pos<<1],mmin[pos<<1|1]);
		}
	}
	inline void del(int pos,int l,int r,int q){
		if(l==r)mmin[pos]=make_pair(1000000000,1000000000);
		else{
			if(q<=mid)del(pos<<1,l,mid,q);
			else del(pos<<1|1,mid+1,r,q);
			mmin[pos]=min(mmin[pos<<1],mmin[pos<<1|1]);
		}
	}
	inline pii query(int pos,int l,int r,int ql,int qr){
		if(ql<=l&&qr>=r)return mmin[pos];
		if(ql<=mid&&qr>mid)return min(query(pos<<1,l,mid,ql,qr),query(pos<<1|1,mid+1,r,ql,qr));
		if(ql<=mid)return query(pos<<1,l,mid,ql,qr);
		return query(pos<<1|1,mid+1,r,ql,qr);
	}
	inline void solve(int ql,int qr){//cerr<<"S "<<ql<<" "<<qr<<endl;
		if(ql>qr)return;
		pii x=query(1,1,m,ql,qr);//cerr<<" "<<x.first<<" "<<x.second<<endl;
		if(x.first<=qr){
			int pos=x.second;
			del(1,1,m,l[pos]);
			update(pos);
			solve(l[pos]+1,qr);
		}
	}
}
namespace M{
	set<int>x,y;
	inline pii query(int pos){//cerr<<endl<<"M "<<pos<<" ";
		auto a=x.upper_bound(pos),b=y.upper_bound(pos);
		return make_pair(b==x.end()?m+1:tr[*b],a==x.begin()?0:*--a);
	}
	inline void ins(int pos){
		x.insert(l[pos]);
		y.insert(r[pos]);
	}
	inline void del(int pos){
		x.erase(l[pos]);
		y.erase(r[pos]);
	}
}
namespace R{
	inline void solve(int l,int r);
}
namespace Q{
	int tag[2000002];
	pii mmin[2000002];
	inline void pushdown(int pos){
		if(tag[pos]){
			tag[pos<<1]+=tag[pos];
			tag[pos<<1|1]+=tag[pos];
			mmin[pos<<1].first+=tag[pos];
			mmin[pos<<1|1].first+=tag[pos];
			tag[pos]=0;
		}
	}
	inline void pushup(int pos){
		mmin[pos]=min(mmin[pos<<1],mmin[pos<<1|1]);
	}
	inline void build(int pos,int l,int r){
		if(l==r)mmin[pos]=make_pair(2100000000,2100000000);
		else{
			build(pos<<1,l,mid);build(pos<<1|1,mid+1,r);pushup(pos);
		}
	}
	inline void add(int pos,int l,int r,int ql,int qr,int v){
		if(ql<=l&&qr>=r)tag[pos]+=v,mmin[pos].first+=v;
		else{
			pushdown(pos);
			if(ql<=mid)add(pos<<1,l,mid,ql,qr,v);
			if(qr>mid)add(pos<<1|1,mid+1,r,ql,qr,v);
			pushup(pos);
		}
	}
	inline void add(int l,int r,int v){
		if(l<=r)add(1,1,m,l,r,v);
	}
	inline void del(int pos,int l,int r,int q){
		if(l==r){
			mmin[pos]=make_pair(2100000000,2100000000);
		}else{
			pushdown(pos);
			if(q<=mid)del(pos<<1,l,mid,q);
			else del(pos<<1|1,mid+1,r,q);
			pushup(pos);
		}
	}
	inline void ins(int pos,int l,int r,int q,int v){
		if(l==r){
			mmin[pos]=make_pair(B::query(G::r[v]-1)-B::query(G::l[v]-1),v);
		}else{
			pushdown(pos);
			if(q<=mid)ins(pos<<1,l,mid,q,v);
			else ins(pos<<1|1,mid+1,r,q,v);
			pushup(pos);
		}
	}
	int now;
	inline void solve(){
		int pos=mmin[1].second;
#ifdef LOCAL
		printf("getans                          ");write(pos,'\n');
#else
		write(pos,' ');
#endif
		if((++now)==n)return;
		del(1,1,m,l[pos]);
		R::solve(l[pos],r[pos]);
		M::del(pos);
		S::del(1,1,m,l[pos]);
		auto pre=M::x.lower_bound(l[pos]),suf=M::y.upper_bound(r[pos]);//cerr<<l[pos]<<" "<<suf<<" ";
		S::solve((pre==M::x.begin()?0:*--pre)+1,(suf==M::y.end()?m+1:*suf)-1);
	}
}
namespace R{
	set<int>res;
	inline void solve(int l,int r){
		for(auto i=res.lower_bound(l),iend=res.lower_bound(r);i!=iend;++i){
			B::add(*i,p[*i]-p[*i+1]);//cerr<<"solved "<<*i<<" "<<*i+1<<" "<<p[*i]<<" "<<p[*i+1]<<" ";
			pii v=M::query(*i);//cerr<<v.first<<" "<<v.second<<endl;
			Q::add(v.first,v.second,p[*i]-p[*i+1]);
		}
	}
}
inline void update(int pos){//cerr<<"update "<<pos<<endl;
	Q::ins(1,1,m,l[pos],pos);
	M::ins(pos);
}
int main() {
	cin>>n;
	F(i,1,n)read(l[i],r[i]),p[++m]=l[i],p[++m]=r[i];
	sort(p+1,p+m+1);
	p[m+1]=1000000000;//F(i,1,m)cerr<<p[i]<<" ";cerr<<endl;
	F(i,1,m)qwq[i]=i;
	F(i,1,n)r[i]=(qwq[lower_bound(p+1,p+m+1,r[i])-p]++);
	UF(i,n,1)l[i]=(qwq[lower_bound(p+1,p+m+1,l[i])-p]++);
	F(i,1,n)tl[l[i]]=i,tr[r[i]]=l[i];
	F(i,1,m)B::add(i,p[i+1]-p[i]),R::res.insert(i);
	memset(temp,0x3f,sizeof(temp));
	memset(Q::mmin,0x7f,sizeof(Q::mmin));
	F(i,1,n)temp[l[i]]=make_pair(r[i],i);//,cerr<<"    "<<l[i]<<" "<<r[i]<<endl;
	S::build(1,1,m);
	F(i,1,n){
		auto pos=M::x.lower_bound(l[i]);//cerr<<tl[*pos]<<endl;
		if(pos==M::x.end()||r[tl[*pos]]>r[i]){
			update(i);
			S::del(1,1,m,l[i]);
		}
	}
	F(i,1,n)Q::solve();
	return 0;
}
Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 39588kb

input:

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

output:

1 2 5 3 4 6

result:

ok 6 tokens

Test #2:

score: 0
Accepted
time: 4ms
memory: 37680kb

input:

4
3 7
10 14
1 6
6 11

output:

1 3 2 4

result:

ok 4 tokens

Test #3:

score: 0
Accepted
time: 3ms
memory: 39716kb

input:

100
50 51
49 51
49 52
48 52
48 53
47 53
47 54
46 54
46 55
45 55
45 56
44 56
44 57
43 57
43 58
42 58
42 59
41 59
41 60
40 60
40 61
39 61
39 62
38 62
38 63
37 63
37 64
36 64
36 65
35 65
35 66
34 66
34 67
33 67
33 68
32 68
32 69
31 69
31 70
30 70
30 71
29 71
29 72
28 72
28 73
27 73
27 74
26 74
26 75
25...

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

result:

ok 100 tokens

Test #4:

score: 0
Accepted
time: 7ms
memory: 37548kb

input:

100
41 42
99 100
47 48
50 51
56 57
61 62
27 28
85 86
44 45
3 4
26 27
20 21
92 93
33 34
86 87
69 70
84 85
62 63
81 82
2 3
13 14
32 33
82 83
70 71
46 47
45 46
19 20
83 84
57 59
63 65
59 61
82 84
45 47
48 50
70 72
42 44
84 86
26 28
61 63
2 4
17 19
65 67
54 56
67 69
96 99
42 45
47 50
34 37
14 17
51 54
7...

output:

1 2 3 4 5 6 7 8 9 10 11 38 12 13 14 15 16 17 37 18 39 19 20 40 21 22 23 24 25 26 33 27 28 32 35 29 30 31 57 73 34 47 71 36 46 41 53 42 58 43 54 44 52 77 45 63 48 62 49 64 80 50 60 79 91 51 66 89 55 65 83 56 59 67 86 61 72 82 90 96 68 75 81 93 69 74 84 92 70 87 88 94 97 99 76 78 85 95 98 100

result:

ok 100 tokens

Test #5:

score: 0
Accepted
time: 3ms
memory: 39804kb

input:

100
26 27
68 69
33 34
96 97
42 43
6 7
60 61
22 23
9 10
19 20
38 39
7 8
73 74
64 65
53 54
84 85
15 16
79 80
62 63
11 12
32 33
80 81
95 96
54 55
83 84
89 90
55 56
74 75
97 98
81 82
23 24
57 58
14 15
34 35
59 60
40 41
46 47
18 19
21 22
56 57
35 36
69 70
82 83
94 95
63 64
86 87
31 32
76 77
39 40
47 48
4...

output:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100

result:

ok 100 tokens

Test #6:

score: -100
Wrong Answer
time: 7ms
memory: 37636kb

input:

100
66 67
42 43
32 33
28 29
96 97
19 20
41 42
38 39
73 74
50 51
31 32
40 41
3 4
72 73
29 30
45 46
14 15
11 12
68 69
21 22
25 26
51 52
75 76
76 77
8 9
99 100
53 54
27 28
61 62
26 27
74 75
84 85
64 65
79 80
71 72
85 86
33 34
0 1
90 91
24 25
4 6
51 53
64 66
34 36
94 96
66 68
97 99
31 33
80 82
19 21
88 ...

output:

1 2 3 4 5 6 7 8 9 10 11 48 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 76 81 31 66 32 33 34 35 36 59 77 37 38 39 40 42 43 46 50 55 64 57 41 44 62 74 78 87 90 45 71 47 49 51 69 80 89 52 53 54 82 56 58 72 60 68 73 61 63 91 65 75 67 79 88 96 98 70 84 94 95 83 85 86 92 93 97 99 100

result:

wrong answer 42nd words differ - expected: '37', found: '77'
English 繁體中文 简体中文

Server Time: 2025-01-20 18:30:47 | OpenSource Project