QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#236903#7517. Flying Ship StorykonyakestRE 334ms3524kbC++232.6kb2023-11-04 11:25:532023-11-04 11:25:53

Judging History

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

  • [2023-11-04 11:25:53]
  • 评测
  • 测评结果:RE
  • 用时:334ms
  • 内存:3524kb
  • [2023-11-04 11:25:53]
  • 提交

answer

#include<bits/stdc++.h>
#include<bits/extc++.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 namespace __gnu_pbds;
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];
	int cnt[maxn];
	gp_hash_table<int,int> table;
	void push(int x,int y,int val){
		table[x]++;
		int tot=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;
				cnt[i]++;
				return;
			}
			if(!mp[i].x) return cnt[i]++,mp[i].x=x,mp[i].y[0]={y,val},debug(i,mp[i]),(void)0;
			tot+=cnt[i];
		}
		int pos=gen()%tot;
		F(i,0,maxn-1){
			pos-=cnt[i];
			if(pos<=0){
				mp[i].x=x,mp[pos].y={make_pair(y,val),make_pair(0,0)};
				cnt[i]=table[x];
				return;
			}
		}
	}
	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;
		}
		debug(xx.table,yy.table);
	}
    return not "FST";
}
/*
 *
 *
 *
 *
 *
 *
 *
 */




Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 314ms
memory: 3524kb

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: 334ms
memory: 3456kb

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
Runtime Error

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:


result: