QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#236903 | #7517. Flying Ship Story | konyakest | RE | 334ms | 3524kb | C++23 | 2.6kb | 2023-11-04 11:25:53 | 2023-11-04 11:25:53 |
Judging History
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...