oj.uz

Submission #318939

# Submission time Handle Problem Language Result Execution time Memory
318939 2020-11-03T13:32:21 Z leaked Klasika (COCI20_klasika) C++14
33 / 110
 1047 ms 524288 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{
    node *a[2];
    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;
}
/*



*/

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 36728 KB Output is correct
2 Correct 41 ms 36964 KB Output is correct
3 Correct 41 ms 37240 KB Output is correct
4 Correct 41 ms 37548 KB Output is correct
5 Correct 40 ms 36580 KB Output is correct
6 Correct 40 ms 36836 KB Output is correct
7 Correct 41 ms 37092 KB Output is correct
8 Correct 42 ms 37604 KB Output is correct
9 Correct 41 ms 36840 KB Output is correct
10 Correct 41 ms 36960 KB Output is correct
11 Correct 41 ms 37220 KB Output is correct
12 Correct 41 ms 37604 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 36728 KB Output is correct
2 Correct 41 ms 36964 KB Output is correct
3 Correct 41 ms 37240 KB Output is correct
4 Correct 41 ms 37548 KB Output is correct
5 Correct 40 ms 36580 KB Output is correct
6 Correct 40 ms 36836 KB Output is correct
7 Correct 41 ms 37092 KB Output is correct
8 Correct 42 ms 37604 KB Output is correct
9 Correct 41 ms 36840 KB Output is correct
10 Correct 41 ms 36960 KB Output is correct
11 Correct 41 ms 37220 KB Output is correct
12 Correct 41 ms 37604 KB Output is correct
13 Correct 47 ms 39908 KB Output is correct
14 Correct 53 ms 43892 KB Output is correct
15 Correct 65 ms 48040 KB Output is correct
16 Correct 65 ms 51940 KB Output is correct
17 Correct 46 ms 39652 KB Output is correct
18 Correct 56 ms 43620 KB Output is correct
19 Correct 59 ms 47716 KB Output is correct
20 Correct 64 ms 51556 KB Output is correct
21 Correct 47 ms 39784 KB Output is correct
22 Correct 52 ms 43620 KB Output is correct
23 Correct 60 ms 47844 KB Output is correct
24 Correct 63 ms 51556 KB Output is correct

Subtask #3
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1047 ms 524288 KB Output is correct
2 Runtime error 1002 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 36728 KB Output is correct
2 Correct 41 ms 36964 KB Output is correct
3 Correct 41 ms 37240 KB Output is correct
4 Correct 41 ms 37548 KB Output is correct
5 Correct 40 ms 36580 KB Output is correct
6 Correct 40 ms 36836 KB Output is correct
7 Correct 41 ms 37092 KB Output is correct
8 Correct 42 ms 37604 KB Output is correct
9 Correct 41 ms 36840 KB Output is correct
10 Correct 41 ms 36960 KB Output is correct
11 Correct 41 ms 37220 KB Output is correct
12 Correct 41 ms 37604 KB Output is correct
13 Correct 47 ms 39908 KB Output is correct
14 Correct 53 ms 43892 KB Output is correct
15 Correct 65 ms 48040 KB Output is correct
16 Correct 65 ms 51940 KB Output is correct
17 Correct 46 ms 39652 KB Output is correct
18 Correct 56 ms 43620 KB Output is correct
19 Correct 59 ms 47716 KB Output is correct
20 Correct 64 ms 51556 KB Output is correct
21 Correct 47 ms 39784 KB Output is correct
22 Correct 52 ms 43620 KB Output is correct
23 Correct 60 ms 47844 KB Output is correct
24 Correct 63 ms 51556 KB Output is correct
25 Correct 1047 ms 524288 KB Output is correct
26 Runtime error 1002 ms 524288 KB Execution killed with signal 9 (could be triggered by violating memory limits)
27 Halted 0 ms 0 KB -