oj.uz

Submission #318940

# Submission time Handle Problem Language Result Execution time Memory
318940 2020-11-03T13:33:38 Z leaked Klasika (COCI20_klasika) C++14
33 / 110
 573 ms 524292 KB 
#include<bits/stdc++.h>

using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
//
//    #pragma GCC optimize("-O3")
//    #pragma GCC optimize("no-stack-protector")
//    #pragma GCC optimize("fast-math")
//    #pragma GCC optimize("Ofast")
//    #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//    #pragma GCC target("avx,avx2,fma")
//    #pragma GCC optimization ("unroll-loops")
//#define LOCAL
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifndef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define f first
#define vec vector
#define s second
#define p_b push_back
#define pb push_back
////////////////////////////////???????????????CHECK THIS OUT???????????????//////////////////////////////
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<long long,long long> pll;
typedef pair<int,int> pii;
typedef pair<long long,int> pli;
////////////////////////////////???????????????CHECK THIS OUT???????????????//////////////////////////////
#define m_p make_pair
#define fast_io cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);
#define all(x) x.begin(),x.end()
#define pw(x) (1ll << x)
#define sz(x) (int)x.size()
#define endl "\n"
#define rall(x) x.rbegin(),x.rend()
//#define int long long
using namespace __gnu_pbds;
ld eps = (ld)1 / 1e6;
const ld pi=3.14159265359;
int inf = 1e9,mod1=1e9+7;
ll sqr(ll a) { return a * a; }
ll qb(ll a) { return a * a * a; }
template<typename T> bool umax(T& a, T b) {return a<b?a=b,1:0;}
template<typename T> bool umin(T& a, T b) {return b<a?a=b,1:0;}
bool is_prime(ll val){for(ll i=2;i<=sqrt(val);i++)if(val%i==0)return 0; return 1;}
ll gcd(ll a, ll b) { return !a ? b : gcd(b % a, a); }
ll binpow(ll a, ll b, ll mod) { return b ? (b % 2 ? (a * (sqr(binpow(a, b / 2, mod)) % mod)) % mod : sqr(binpow(a, b / 2, mod)) % mod) : 1; }ll binmult(ll a, ll b, ll mod) { return b ? (b % 2 ? (2 * binmult(a, b / 2, mod) + a) % mod : (2 * binmult(a, b / 2, mod)) % mod) : 0; }
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
const ll RR=1e4;
const ll tx[8]={1,-1,2,-2,-1,-2};
const ll ty[8]={-2,-2,-1,-1,2,1};
const char rev_to[4]={'E','W','N','S'};
///////////////////fdsfsdfgdsjgdjfsgdsfsdkafsdaokfsdpofdckokfpgjvdsujbgdfpiodjOFCjs;igsd;cpjzckpdoskvgdok;a///////
const int ppp=73;
const int M=1e9+7;
///////////////////fdsfsdfgdsjgdjfsgdsfsdkafsdaokfsdpofdckokfpgjvdsujbgdfpiodjOFCjs;igsd;cpjzckpdoskvgdok;a///////
//const int ppp=73;
const int block=600;
const int OPEN=1;
const int CLOSE=0;
//typedef tree<pli,null_type,less<pli>,rb_tree_tag,tree_order_statistics_node_update> o_st;
auto rnd=bind(uniform_int_distribution<int>(1,5969699),mt19937(time(0)));
void bad(){
    cout<<"-1";
    exit(0);
}
const int N=2e5+4;
const int lg=30;
int in[N],out[N];
int up[lg][N];
int xr[N];
vec<int>g[N];
int ti;
int n=1;
map<int,int>mp;
map<int,int>obr;
void dfs1(int v,int p){
    in[v]=++ti;
    xr[v]=xr[p]^obr[v];
    if(v==p)
        xr[v]=0;
    for(auto &z : g[v]){
        if(z^p)
            dfs1(z,v);
    }
//    debug()<<imie(v)imie(xr[v]);
    out[v]=ti;
}
struct query{
    int tp,x,y;
    query(string s,int _x,int _y){
        tp=(s=="Add"?1:2);
        x=_x;y=_y;
    }
};
struct node{
    gp_hash_table<int,node*>a;
    int cl;
    node(){
        a[0]=a[1]=nullptr;
        cl=0;
    }
};
void add(node* root,int x){
    node  *cur=root;
    cur->cl++;
    for(int i=lg-1;i>=0;i--){
        int bt=(x>>i)&1;
        if(!cur->a[bt]){
            cur->a[bt]=new node();
        }
        cur=cur->a[bt];
        cur->cl++;
    }
}
int GET(node *root,int x){
    if(!root->cl){
        return 0;
    }
    int sub=0;
    node *cur=root;
    for(int i=lg-1;i>=0;i--){
        int bt=(x>>i)&1;
        if(cur->a[bt^1] && cur->a[bt^1]->cl){
            cur=cur->a[bt^1];
            sub+=(1<<i);
        }
        else{
            cur=cur->a[bt];
        }
    }
    return sub;
}
node* t[4*N];
void upd(int id,int vl,int v=1,int tl=1,int tr=n){
    if(tl==tr){
        add(t[v],vl);
        return;
    }
    int tm=(tl+tr)>>1;
    if(tm>=id)
        upd(id,vl,2*v,tl,tm);
    else
        upd(id,vl,2*v+1,tm+1,tr);
    add(t[v],vl);
}
int get(int l,int r,int x,int v=1,int tl=1,int tr=n){
    if(tl>=l && tr<=r){
        return GET(t[v],x);
    }
    if(tl>r || tr<l)
        return 0;
    int tm=(tl+tr)>>1;
    return max(get(l,r,x,2*v,tl,tm),get(l,r,x,2*v+1,tm+1,tr));
}
signed main()
{
    fast_io;
    for(int i=0;i<4*N;i++)
        t[i]=new node();
    int t;
    cin>>t;
    vec<query>q;
    mp[1]=1;
    obr[1]=1;
    for(int i=0;i<t;i++){
        int x,y;
        string s;
        cin>>s>>x>>y;
        query lel=query(s,x,y);
        q.pb(lel);
        if(q[i].tp==1){
            int a=x,b=++n;
            mp[y]=n;
            obr[n]=y;
            g[a].pb(b);
            q[i].x=a,q[i].y=b;
//            debug()<<imie(a)imie(b);
        }
        else{
            int a=x,b=y;
            q[i].x=a,q[i].y=b;
        }
    }
    dfs1(1,1);
    upd(1,0);
    for(int i=0;i<t;i++){
        if(q[i].tp==1){
            int id=q[i].y;
            upd(in[id],xr[id]);
//            debug()<<imie(id)imie(xr[id]);
        }
        else{
            int x=xr[q[i].x];
            int l=in[q[i].y],r=out[q[i].y];
//            debug()<<imie(l)imie(r);
            cout<<get(l,r,x)<<endl;
        }
//        debug()<<imie("YE");
    }
    return 0;
}
/*
12
Query 1 1
Query 1 1
Add 1 306021296
Query 2 2
Query 1 2
Query 1 2
Query 2 2
Query 2 2
Query 1 1
Add 2 15913938
Query 3 2
Query 2 1


*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 277604 KB Output is correct
2 Correct 239 ms 279396 KB Output is correct
3 Correct 244 ms 282980 KB Output is correct
4 Correct 249 ms 285796 KB Output is correct
5 Correct 242 ms 276708 KB Output is correct
6 Correct 244 ms 279400 KB Output is correct
7 Correct 240 ms 282340 KB Output is correct
8 Correct 245 ms 286308 KB Output is correct
9 Correct 238 ms 277092 KB Output is correct
10 Correct 243 ms 280676 KB Output is correct
11 Correct 243 ms 283744 KB Output is correct
12 Correct 245 ms 286180 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 277604 KB Output is correct
2 Correct 239 ms 279396 KB Output is correct
3 Correct 244 ms 282980 KB Output is correct
4 Correct 249 ms 285796 KB Output is correct
5 Correct 242 ms 276708 KB Output is correct
6 Correct 244 ms 279400 KB Output is correct
7 Correct 240 ms 282340 KB Output is correct
8 Correct 245 ms 286308 KB Output is correct
9 Correct 238 ms 277092 KB Output is correct
10 Correct 243 ms 280676 KB Output is correct
11 Correct 243 ms 283744 KB Output is correct
12 Correct 245 ms 286180 KB Output is correct
13 Correct 286 ms 310116 KB Output is correct
14 Correct 312 ms 350436 KB Output is correct
15 Correct 353 ms 393572 KB Output is correct
16 Correct 386 ms 433252 KB Output is correct
17 Correct 268 ms 308068 KB Output is correct
18 Correct 309 ms 348408 KB Output is correct
19 Correct 351 ms 391396 KB Output is correct
20 Correct 391 ms 431844 KB Output is correct
21 Correct 281 ms 308708 KB Output is correct
22 Correct 312 ms 349072 KB Output is correct
23 Correct 360 ms 391544 KB Output is correct
24 Correct 387 ms 431460 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 573 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 240 ms 277604 KB Output is correct
2 Correct 239 ms 279396 KB Output is correct
3 Correct 244 ms 282980 KB Output is correct
4 Correct 249 ms 285796 KB Output is correct
5 Correct 242 ms 276708 KB Output is correct
6 Correct 244 ms 279400 KB Output is correct
7 Correct 240 ms 282340 KB Output is correct
8 Correct 245 ms 286308 KB Output is correct
9 Correct 238 ms 277092 KB Output is correct
10 Correct 243 ms 280676 KB Output is correct
11 Correct 243 ms 283744 KB Output is correct
12 Correct 245 ms 286180 KB Output is correct
13 Correct 286 ms 310116 KB Output is correct
14 Correct 312 ms 350436 KB Output is correct
15 Correct 353 ms 393572 KB Output is correct
16 Correct 386 ms 433252 KB Output is correct
17 Correct 268 ms 308068 KB Output is correct
18 Correct 309 ms 348408 KB Output is correct
19 Correct 351 ms 391396 KB Output is correct
20 Correct 391 ms 431844 KB Output is correct
21 Correct 281 ms 308708 KB Output is correct
22 Correct 312 ms 349072 KB Output is correct
23 Correct 360 ms 391544 KB Output is correct
24 Correct 387 ms 431460 KB Output is correct
25 Runtime error 573 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
26 Halted 0 ms 0 KB -