QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#236884#7517. Flying Ship StorykonyakestTL 322ms3468kbC++232.4kb2023-11-04 11:17:222023-11-04 11:17:24

Judging History

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

  • [2023-11-04 11:17:24]
  • 评测
  • 测评结果:TL
  • 用时:322ms
  • 内存:3468kb
  • [2023-11-04 11:17:22]
  • 提交

answer

#include<bits/stdc++.h>
#define F(i,j,k) for(auto i=j;i<=(decltype(j))(k);i++)
#define exec(...) [&](){__VA_ARGS__}()
#define view(x) begin(x),end(x)
#define pb push_back
#define lambda [&]
#define x first
#define y second
#define endl '\n'
#define os ostream
using namespace std;
using ll=long long;
template<typename T>void ckmin(T& a,T b){(a>b)&&(a=b);}
template<typename T>void ckmax(T& a,T b){(a<b)&&(a=b);}

#ifdef DEBUG
template<typename ...T>os& operator<<(os& out,tuple<T...> x);

template<typename T1,typename T2>os& operator<<(os& out,pair<T1,T2> x){return out<<tuple(x);}
template<typename T,typename=decltype(T().begin()),typename=enable_if_t<!is_same_v<decay_t<T>,string>>>os& operator<<(os& out,T x){return out<<"{",exec(auto n=0u;for(auto i:x) out<<i<<(++n==x.size()?"":",");),out<<"}";}
template<typename ...T>os& operator<<(os& out,tuple<T...> x){return apply(lambda(T... xx){auto n=0u;out<<"{";((out<<xx<<(++n==sizeof...(T)?"":",")),...),out<<"}";},x),out;}
#define debug(...) cerr<<"#"<<__LINE__<<": "<<#__VA_ARGS__<<" = "<<tuple(__VA_ARGS__)<<endl
#else
#define debug(...) (void)0
#endif

const int maxn=305;

mt19937 gen(random_device{}());

struct DATA{
	pair<int,array<pair<int,int>,2>> mp[maxn];
	void push(int x,int y,int val){
		int mx=0,pos=0;
		F(i,0,maxn-1){
			if(mp[i].x==x){
				auto p=mp[i].y;
				if(y==p[0].x) ckmax(p[0].y,val);
				else if(y==p[1].x) ckmax(p[1].y,val);
				else p[1]={y,val};
				if(p[0].y<p[1].y) swap(p[0],p[1]);
				mp[i].y=p;
				return;
			}
			if(!mp[i].x) return mp[i].x=x,mp[i].y[0]={y,val},debug(i,mp[i]),(void)0;
			if(mp[i].y[0].y>mx&&gen()%100==1) mx=mp[i].y[0].y,pos=i;
		}
		if(val>mx) mp[pos].x=x,mp[pos].y={make_pair(y,val),make_pair(0,0)};
	}
	int get(int x,int y){
		int mx=0;
		F(i,0,maxn-1) if(mp[i].x&&mp[i].x!=x){
			if(mp[i].y[0].x!=y) ckmax(mx,mp[i].y[0].y);
			if(mp[i].y[1].x!=y) ckmax(mx,mp[i].y[1].y);
		}
		return mx;
	}
}xx,yy;

int n,x,y,z,op,lastans;

int cnt;

signed main(){
    cin.tie(0)->sync_with_stdio(0);
	cin>>n;
	F(i,1,n){
		cin>>op;
		if(op==1){
			cin>>x>>y>>z;
			x^=lastans,y^=lastans,z^=lastans;
			debug(x,y,z);
			xx.push(x,y,z),yy.push(y,x,z);
		}
		else{
			cin>>x>>y;
			x^=lastans,y^=lastans,z^=lastans;
			debug(x,y);
			cnt++;
			int ans=(lastans=max(xx.get(x,y),yy.get(y,x)));
			cout<<ans<<endl;
		}
	}
    return not "FST";
}
/*
 *
 *
 *
 *
 *
 *
 *
 */




Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3468kb

input:

5
1 2 3 1
1 4 5 2
2 2 2
2 3 7
2 3 4

output:

2
1
0

result:

ok 3 lines

Test #2:

score: 0
Accepted
time: 322ms
memory: 3436kb

input:

1000000
2 370943499 431961772
1 1 1 11995570
2 37566858 838793045
1 11995571 11995569 908148975
2 11995571 11995571
1 1 3 716821068
2 67877937 3
1 11995571 11995571 771898489
2 38381714 99749723
1 915818844 915818847 729541681
2 592361351 915818846
1 783627722 783627722 639375021
2 102203700 8636489...

output:

0
11995570
0
11995570
915818845
783627723
915818845
0
0
915818845
0
783627723
0
904468304
904468304
904468304
915818845
904468304
915818845
904468304
915818845
0
904468304
0
915818845
915818845
0
0
915818845
915818845
0
921710773
0
921710773
998138906
921710773
0
921710773
998138906
0
998138906
0
99...

result:

ok 500000 lines

Test #3:

score: 0
Accepted
time: 316ms
memory: 3416kb

input:

1000000
2 648544745 437316088
1 1 1 221075686
2 802693951 691188141
1 221075687 221075684 1036811136
2 771835961 178451319
1 820061031 820061031 560017372
2 829408420 820061028
1 293604539 293604539 699366423
2 293604539 293604539
1 1 2 610044241
2 50747012 885321059
1 942633132 942633132 603537610
...

output:

0
221075686
820061030
293604538
0
942633133
942633133
27478144
820061030
820061030
900696946
27478144
942633133
942633133
0
772167494
27478144
891145650
900696946
772167494
891145650
918281274
772167494
772167494
772167494
772167494
772167494
942633133
918281274
891145650
918281274
891145650
8911456...

result:

ok 500000 lines

Test #4:

score: -100
Time Limit Exceeded

input:

1000000
2 488777832 43440411
1 441939805 62137297 1349
2 198318033 382339804
1 441938456 72190649 815
2 458351680 72190649
1 441938456 287971850 290
2 161496970 653240491
1 933968337 49827233 1142
2 441938231 49827233
1 623590902 306969890 440
2 441939805 144230480
1 441939265 480404387 11460
2 4419...

output:

0
1349
1349
1642
0
540
440
440
440
11992
4593
4228
9603
4228
12488
7139
4593
14051
14051
14051
16301
4593
20640
14051
34628
20640
34628
35421
34628
34628
49987
11225
17743
11225
17743
35421
17743
35421
17743
49987
56227
56227
11225
11225
56227
56227
56227
56227
56227
37643
37643
49987
37643
37643
21...

result: