QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#114115	#2759. The Big Prize	Crysfly	100 ✓	25ms	26008kb	C++17	1.7kb	2023-06-21 09:05:58	2023-06-21 09:06:01

Judging History

This is the latest submission verdict.

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-06-21 09:06:01]
Judged

Verdict: 100
Time: 25ms
Memory: 26008kb

Show

[2023-06-21 09:05:58]
Submitted

answer

#include "prize.h"
// what is matter? never mind. 
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
//#define int long long
using namespace std;

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 200005
#define inf 0x3f3f3f3f

int a[maxn][2];
int query(int i){
	vi o=ask(i-1);
	a[i][0]=o[0],a[i][1]=o[1];
//	cout<<"ask "<<i<<" "<<a[i][0]<<" "<<a[i][1]<<endl;
	return !a[i][0]&&!a[i][1];
}

int ql[maxn<<3],qr[maxn<<3],tag[maxn<<3];
void build(int p,int l,int r){
	if(l>r)return;
	ql[p]=l,qr[p]=r;
	int mid=l+r>>1;
	build(p<<1,l,mid-1);
	build(p<<1|1,mid+1,r); 
}
void push(int p,int l,int r,int nl,int nr){
	if(tag[p])return;
	if(l>=nl&&r<=nr)return tag[p]=1,void();
	int mid=l+r>>1;
	if(nl<=mid-1)push(p<<1,l,mid-1,nl,nr);
	if(nr>mid)push(p<<1|1,mid+1,r,nl,nr);
}
int qtag(int p){
	int res=tag[p];
	while(p>>=1)res|=tag[p];
	return res;
}

set<int>s[maxn];

int find_best(int n)
{
	build(1,1,n);
	queue<int>q; q.push(1);
	while(q.size()){
		int p=q.front(); q.pop();
		if(qtag(p))continue;
		int l=ql[p],r=qr[p],u=l+r>>1;
		if(query(u))return u-1;
		int t=a[u][0]+a[u][1];
		if(!s[t].size()) s[t].insert(0),s[t].insert(n+1);
		auto R=s[t].lower_bound(u),L=prev(R);
		s[t].insert(u);
		if((*R)<=n){
			int tmp=a[u][0]+a[*R][1];
			if(tmp==t)push(1,1,n,u,*R);
		}
		if((*L)>=1){
			int tmp=a[*L][0]+a[u][1];
			if(tmp==t)push(1,1,n,*L,u);
		}
		if(l<=u-1) q.push(p<<1);
		if(u+1<=r) q.push(p<<1|1);
	}
	assert(0);
}
/*
16
2 2 1 2 2 2 2 2 2 2 2 2 2 2 2 2
*/

源文件, 语言: C++17

详细

Subtask #1:

score: 20

Accepted

Test #1:

score: 20

Accepted

time: 3ms

memory: 22452kb

input:

output:

result:

ok

Test #2:

score: 0

Accepted

time: 3ms

memory: 22508kb

input:

output:

result:

ok

Test #3:

score: 0

Accepted

time: 3ms

memory: 23752kb

input:

output:

result:

ok

Test #4:

score: 0

Accepted

time: 1ms

memory: 20644kb

input:

output:

result:

ok

Test #5:

score: 0

Accepted

time: 7ms

memory: 23732kb

input:

output:

result:

ok

Test #6:

score: 0

Accepted

time: 2ms

memory: 24196kb

input:

output:

result:

ok

Test #7:

score: 0

Accepted

time: 2ms

memory: 23920kb

input:

output:

result:

ok

Test #8:

score: 0

Accepted

time: 5ms

memory: 24272kb

input:

output:

result:

ok

Test #9:

score: 0

Accepted

time: 6ms

memory: 20744kb

input:

200000
0 0

output:

A 99999
B 99999

result:

ok

Test #10:

score: 0

Accepted

time: 0ms

memory: 19492kb

input:

output:

result:

ok

Subtask #2:

score: 80

Accepted

Test #11:

score: 80

Accepted

time: 0ms

memory: 19472kb

input:

output:

result:

ok

Test #12:

score: 80

Accepted

time: 6ms

memory: 19512kb

input:

output:

result:

ok

Test #13:

score: 80

Accepted

time: 7ms

memory: 24488kb

input:

output:

result:

ok

Test #14:

score: 80

Accepted

time: 3ms

memory: 24028kb

input:

output:

result:

ok

Test #15:

score: 80

Accepted

time: 6ms

memory: 17344kb

input:

output:

result:

ok

Test #16:

score: 80

Accepted

time: 4ms

memory: 20696kb

input:

output:

result:

ok

Test #17:

score: 80

Accepted

time: 7ms

memory: 20816kb

input:

output:

result:

ok

Test #18:

score: 80

Accepted

time: 4ms

memory: 24092kb

input:

output:

result:

ok

Test #19:

score: 80

Accepted

time: 1ms

memory: 20752kb

input:

200000
0 0

output:

A 99999
B 99999

result:

ok

Test #20:

score: 80

Accepted

time: 0ms

memory: 19416kb

input:

output:

result:

ok

Test #21:

score: 80

Accepted

time: 8ms

memory: 20908kb

input:

output:

result:

ok

Test #22:

score: 80

Accepted

time: 9ms

memory: 24548kb

input:

output:

result:

ok

Test #23:

score: 80

Accepted

time: 5ms

memory: 24576kb

input:

output:

result:

ok

Test #24:

score: 80

Accepted

time: 1ms

memory: 20372kb

input:

output:

result:

ok

Test #25:

score: 80

Accepted

time: 10ms

memory: 25284kb

input:

output:

result:

ok

Test #26:

score: 80

Accepted

time: 1ms

memory: 25324kb

input:

output:

result:

ok

Test #27:

score: 80

Accepted

time: 11ms

memory: 21244kb

input:

output:

result:

ok

Test #28:

score: 80

Accepted

time: 3ms

memory: 25320kb

input:

output:

result:

ok

Test #29:

score: 80

Accepted

time: 9ms

memory: 25312kb

input:

output:

result:

ok

Test #30:

score: 80

Accepted

time: 4ms

memory: 19992kb

input:

output:

result:

ok

Test #31:

score: 80

Accepted

time: 15ms

memory: 23268kb

input:

output:

result:

ok

Test #32:

score: 80

Accepted

time: 1ms

memory: 20736kb

input:

output:

result:

ok

Test #33:

score: 80

Accepted

time: 1ms

memory: 17628kb

input:

output:

result:

ok

Test #34:

score: 80

Accepted

time: 1ms

memory: 24308kb

input:

output:

result:

ok

Test #35:

score: 80

Accepted

time: 25ms

memory: 21092kb

input:

output:

result:

ok

Test #36:

score: 80

Accepted

time: 7ms

memory: 21172kb

input:

output:

result:

ok

Test #37:

score: 80

Accepted

time: 2ms

memory: 19324kb

input:

output:

result:

ok

Test #38:

score: 80

Accepted

time: 10ms

memory: 25232kb

input:

output:

result:

ok

Test #39:

score: 80

Accepted

time: 10ms

memory: 21156kb

input:

output:

result:

ok

Test #40:

score: 80

Accepted

time: 10ms

memory: 21292kb

input:

output:

result:

ok

Test #41:

score: 80

Accepted

time: 9ms

memory: 20892kb

input:

output:

result:

ok

Test #42:

score: 80

Accepted

time: 11ms

memory: 18212kb

input:

output:

result:

ok

Test #43:

score: 80

Accepted

time: 3ms

memory: 20412kb

input:

output:

A 49
A 24
A 74
A 11
A 36
A 61
A 87
A 5
A 42
A 67
A 80
A 93
A 2
A 8
A 45
A 64
A 70
A 77
A 90
A 96
A 0
A 3
B 3

result:

ok

Test #44:

score: 80

Accepted

time: 6ms

memory: 20904kb

input:

output:

result:

ok

Test #45:

score: 80

Accepted

time: 1ms

memory: 24272kb

input:

output:

result:

ok

Test #46:

score: 80

Accepted

time: 8ms

memory: 21288kb

input:

output:

result:

ok

Test #47:

score: 80

Accepted

time: 7ms

memory: 20848kb

input:

output:

result:

ok

Test #48:

score: 80

Accepted

time: 0ms

memory: 19376kb

input:

output:

result:

ok

Test #49:

score: 80

Accepted

time: 5ms

memory: 21224kb

input:

output:

result:

ok

Test #50:

score: 80

Accepted

time: 8ms

memory: 25236kb

input:

output:

result:

ok

Test #51:

score: 80

Accepted

time: 19ms

memory: 25416kb

input:

output:

result:

ok

Test #52:

score: 80

Accepted

time: 18ms

memory: 21456kb

input:

output:

result:

ok

Test #53:

score: 80

Accepted

time: 15ms

memory: 23264kb

input:

output:

result:

ok

Test #54:

score: 80

Accepted

time: 6ms

memory: 21384kb

input:

output:

result:

ok

Test #55:

score: 80

Accepted

time: 10ms

memory: 25308kb

input:

output:

result:

ok

Test #56:

score: 80

Accepted

time: 8ms

memory: 21252kb

input:

output:

result:

ok

Test #57:

score: 80

Accepted

time: 11ms

memory: 21252kb

input:

output:

result:

ok

Test #58:

score: 80

Accepted

time: 6ms

memory: 25364kb

input:

output:

result:

ok

Test #59:

score: 80

Accepted

time: 9ms

memory: 21192kb

input:

output:

result:

ok

Test #60:

score: 80

Accepted

time: 14ms

memory: 20752kb

input:

output:

result:

ok

Test #61:

score: 80

Accepted

time: 19ms

memory: 23288kb

input:

output:

result:

ok

Test #62:

score: 80

Accepted

time: 16ms

memory: 23344kb

input:

output:

result:

ok

Test #63:

score: 80

Accepted

time: 3ms

memory: 19432kb

input:

output:

result:

ok

Test #64:

score: 80

Accepted

time: 7ms

memory: 19204kb

input:

output:

result:

ok

Test #65:

score: 80

Accepted

time: 5ms

memory: 21244kb

input:

output:

result:

ok

Test #66:

score: 80

Accepted

time: 1ms

memory: 23396kb

input:

output:

result:

ok

Test #67:

score: 80

Accepted

time: 18ms

memory: 25432kb

input:

output:

result:

ok

Test #68:

score: 80

Accepted

time: 7ms

memory: 21292kb

input:

output:

result:

ok

Test #69:

score: 80

Accepted

time: 3ms

memory: 21436kb

input:

output:

result:

ok

Test #70:

score: 80

Accepted

time: 6ms

memory: 20788kb

input:

output:

result:

ok

Test #71:

score: 80

Accepted

time: 4ms

memory: 24320kb

input:

output:

result:

ok

Test #72:

score: 80

Accepted

time: 3ms

memory: 21856kb

input:

output:

result:

ok

Test #73:

score: 80

Accepted

time: 0ms

memory: 19408kb

input:

output:

result:

ok

Test #74:

score: 80

Accepted

time: 0ms

memory: 24056kb

input:

output:

result:

ok

Test #75:

score: 80

Accepted

time: 7ms

memory: 24316kb

input:

output:

result:

ok

Test #76:

score: 80

Accepted

time: 3ms

memory: 22476kb

input:

output:

result:

ok

Test #77:

score: 80

Accepted

time: 8ms

memory: 23764kb

input:

output:

result:

ok

Test #78:

score: 80

Accepted

time: 1ms

memory: 23888kb

input:

output:

result:

ok

Test #79:

score: 80

Accepted

time: 0ms

memory: 21008kb

input:

output:

result:

ok

Test #80:

score: 80

Accepted

time: 6ms

memory: 20796kb

input:

output:

result:

ok

Test #81:

score: 80

Accepted

time: 8ms

memory: 26008kb

input:

output:

result:

ok

Test #82:

score: 80

Accepted

time: 0ms

memory: 22712kb

input:

output:

result:

ok

Test #83:

score: 80

Accepted

time: 22ms

memory: 25792kb

input:

output:

result:

ok

Test #84:

score: 80

Accepted

time: 10ms

memory: 25888kb

input:

output:

result:

ok

Test #85:

score: 80

Accepted

time: 8ms

memory: 21132kb

input:

output:

result:

ok

Test #86:

score: 80

Accepted

time: 9ms

memory: 19956kb

input:

output:

result:

ok

Test #87:

score: 80

Accepted

time: 5ms

memory: 20976kb

input:

output:

result:

ok

Test #88:

score: 80

Accepted

time: 3ms

memory: 20916kb

input:

output:

result:

ok

Test #89:

score: 80

Accepted

time: 9ms

memory: 21140kb

input:

output:

result:

ok

Test #90:

score: 80

Accepted

time: 24ms

memory: 25848kb

input:

output:

result:

ok

Test #91:

score: 80

Accepted

time: 11ms

memory: 25508kb

input:

output:

result:

ok

Test #92:

score: 80

Accepted

time: 11ms

memory: 23472kb

input:

output:

result:

ok

Test #93:

score: 80

Accepted

time: 7ms

memory: 17584kb

input:

output:

result:

ok

Test #94:

score: 80

Accepted

time: 6ms

memory: 23584kb

input:

output:

result:

ok

Test #95:

score: 80

Accepted

time: 16ms

memory: 21228kb

input:

output:

result:

ok

Test #96:

score: 80

Accepted

time: 0ms

memory: 24352kb

input:

output:

result:

ok

Test #97:

score: 80

Accepted

time: 11ms

memory: 24060kb

input:

output:

result:

ok

Test #98:

score: 80

Accepted

time: 14ms

memory: 24556kb

input:

output:

result:

ok

Test #99:

score: 80

Accepted

time: 3ms

memory: 24484kb

input:

output:

result:

ok

Test #100:

score: 80

Accepted

time: 4ms

memory: 19248kb

input:

output:

result:

ok

Test #101:

score: 80

Accepted

time: 8ms

memory: 20944kb

input:

output:

result:

ok

Test #102:

score: 80

Accepted

time: 0ms

memory: 20996kb

input:

output:

result:

ok

Test #103:

score: 80

Accepted

time: 1ms

memory: 20712kb

input:

output:

result:

ok

Test #104:

score: 80

Accepted

time: 6ms

memory: 20768kb

input:

output:

result:

ok

Test #105:

score: 80

Accepted

time: 16ms

memory: 24296kb

input:

output:

result:

ok

Test #106:

score: 80

Accepted

time: 0ms

memory: 20704kb

input:

output:

A 99999
A 49999
A 149999
A 24999
A 74999
A 124999
A 174999
A 12499
A 37499
A 87499
A 112499
A 137499
A 162499
A 187499
A 6249
A 31249
A 43749
A 81249
A 93749
A 106249
A 118749
A 131249
A 168749
A 181249
A 193749
A 3124
A 9374
A 34374
A 46874
A 78124
A 84374
A 90624
A 96874
A 103124
A 115624
A 121874...

result:

ok

Test #107:

score: 80

Accepted

time: 5ms

memory: 24348kb

input:

output:

result:

ok

Extra Test:

score: 0

Extra Test Passed