Submission #782148

#	Time	Username	Problem	Language	Result	Execution time	Memory
782148		FatihSolak	Game (IOI13_game)	C++17	100 / 100	2247 ms	155392 KiB

game

#include "game.h"
#include <bits/stdc++.h>
#define N 4000005
using namespace std;
int R,C;

struct node1{
    long long val;
    int l,r;
    int lc,rc;
    node1():lc(0),rc(0),val(0){

    }
}t1[N];
int cnt1 = 1;
struct SegTree{
    int root;
    SegTree():root(0){

    }
    void upd(int v,int pos,long long val){
        if(t1[v].l == t1[v].r){
            t1[v].val = val;
            return;
        }
        if(t1[v].lc != 0 && t1[t1[v].lc].l <= pos && pos <= t1[t1[v].lc].r){
            upd(t1[v].lc,pos,val);
            t1[v].val = __gcd(t1[t1[v].lc].val,t1[t1[v].rc].val);
            return;
        }
        if(t1[v].rc != 0 && t1[t1[v].rc].l <= pos && pos <= t1[t1[v].rc].r){
            upd(t1[v].rc,pos,val);
            t1[v].val = __gcd(t1[t1[v].lc].val,t1[t1[v].rc].val);
            return;
        }
        int tm = (t1[v].l + t1[v].r)/2;
        if(t1[v].lc == 0 && pos <= tm){
            t1[v].lc = cnt1++;
            t1[t1[v].lc].val = val;
            t1[t1[v].lc].l = pos;
            t1[t1[v].lc].r = pos; 
            t1[v].val = __gcd(t1[t1[v].lc].val,t1[t1[v].rc].val);
            return;
        }
        if(t1[v].rc == 0 && pos > tm){
            t1[v].rc = cnt1++;
            t1[t1[v].rc].val = val;
            t1[t1[v].rc].l = pos;
            t1[t1[v].rc].r = pos; 
            t1[v].val = __gcd(t1[t1[v].lc].val,t1[t1[v].rc].val);
            return;
        }
        if(pos <= tm){
            int tmp = t1[v].lc;
            t1[v].lc = cnt1++;
            t1[t1[v].lc].l = t1[v].l;
            t1[t1[v].lc].r = tm;
            while(1){
                int tmm = (t1[t1[v].lc].l + t1[t1[v].lc].r)/2;
                if(t1[tmp].r <= tmm && pos <= tmm){
                    t1[t1[v].lc].r = tmm;
                    continue;
                }
                if(t1[tmp].l > tmm && pos > tmm){
                    t1[t1[v].lc].l = tmm + 1;
                    continue;
                }
                break;
            }
            if(pos < t1[tmp].l){
                t1[t1[v].lc].lc = cnt1++;
                t1[t1[v].lc].rc = tmp;
                t1[t1[t1[v].lc].lc].val = val;
                t1[t1[t1[v].lc].lc].l = pos;
                t1[t1[t1[v].lc].lc].r = pos; 
            }
            else{
                t1[t1[v].lc].lc = tmp;   
                t1[t1[v].lc].rc = cnt1++;
                t1[t1[t1[v].lc].rc].val = val;
                t1[t1[t1[v].lc].rc].l = pos;
                t1[t1[t1[v].lc].rc].r = pos; 
            }
            t1[t1[v].lc].val = __gcd(t1[t1[t1[v].lc].lc].val,t1[t1[t1[v].lc].rc].val);
        }
        else{
            int tmp = t1[v].rc;
            t1[v].rc = cnt1++;
            t1[t1[v].rc].l = tm+1;
            t1[t1[v].rc].r = t1[v].r;
            while(1){
                int tmm = (t1[t1[v].rc].l + t1[t1[v].rc].r)/2;
                if(t1[tmp].r <= tmm && pos <= tmm){
                    t1[t1[v].rc].r = tmm;
                    continue;
                }
                if(t1[tmp].l > tmm && pos > tmm){
                    t1[t1[v].rc].l = tmm + 1;
                    continue;
                }
                break;
            }
            if(pos < t1[tmp].l){
                t1[t1[v].rc].lc = cnt1++;
                t1[t1[v].rc].rc = tmp;
                t1[t1[t1[v].rc].lc].val = val;
                t1[t1[t1[v].rc].lc].l = pos;
                t1[t1[t1[v].rc].lc].r = pos; 
            }
            else{
                t1[t1[v].rc].lc = tmp;   
                t1[t1[v].rc].rc = cnt1++;
                t1[t1[t1[v].rc].rc].val = val;
                t1[t1[t1[v].rc].rc].l = pos;
                t1[t1[t1[v].rc].rc].r = pos; 
            }
            t1[t1[v].rc].val = __gcd(t1[t1[t1[v].rc].lc].val,t1[t1[t1[v].rc].rc].val);
        }
        t1[v].val = __gcd(t1[t1[v].lc].val,t1[t1[v].rc].val);
    }
    long long get(int v,int l,int r){
        // cout << v << ' ' << l << ' ' << r << endl;
        // cout << t1[v].l << ' ' << t1[v].r << ' ' <<  t1[v].val << endl;
        if(v == 0 || t1[v].r < l || r < t1[v].l)
            return 0;
        if(l <= t1[v].l && t1[v].r <= r){
            return t1[v].val;
        }
        return __gcd(get(t1[v].lc,l,r),get(t1[v].rc,l,r));
    }
    void upd(int pos,long long val){
        if(root == 0){
            root = cnt1++;
            t1[root].l = 0;
            t1[root].r = C-1;
        }
        upd(root,pos,val);
    }
    long long get(int l,int r){
        //cout << "HEY" << endl;
        return get(root,l,r);
    }
};

struct Node2{
    int lc,rc;
    SegTree t;
    Node2():lc(0),rc(0){

    }
}t2[N];
int cnt2 = 1;
map<int,SegTree> mp;
struct SegTree2D{
    int root;
    SegTree2D():root(0){}

    void upd(int v,int tl,int tr,int pos1,int pos2){
        t2[v].t.upd(pos2,mp[pos2].get(tl,tr));
        if(tl == tr){
            return;
        }
        int tm = (tl + tr)/2;
        if(pos1 <= tm){
            if(t2[v].lc == 0)
                t2[v].lc = cnt2++;
            upd(t2[v].lc,tl,tm,pos1,pos2);
        }
        else{
            if(t2[v].rc == 0)
                t2[v].rc = cnt2++;
            upd(t2[v].rc,tm+1,tr,pos1,pos2);
        }
    }
    long long get(int v,int tl,int tr,int l1,int r1,int l2,int r2){
        //cout << v << ' ' << tl << ' ' << tr << endl;
        if(v == 0 || tr < l1 || r1 < tl){
            return 0;
        }
        if(l1 <= tl && tr <= r1){
            return t2[v].t.get(l2,r2);
        }
        int tm = (tl + tr)/2;
        return __gcd(get(t2[v].lc,tl,tm,l1,r1,l2,r2),get(t2[v].rc,tm+1,tr,l1,r1,l2,r2));
    }
    void upd(int pos1,int pos2){
        if(root == 0){
            root = cnt2++;
        }
        upd(root,0,R-1,pos1,pos2);
    }
    long long get(int l1,int r1,int l2,int r2){
        return get(root, 0, R-1, l1, r1, l2, r2);
    }
}tree;

void init(int r, int c) {
    R = 1e9;
    C = 1e9;
}
void update(int P, int Q, long long K) {
    mp[Q].upd(P,K);
    tree.upd(P,Q);
}

long long calculate(int P, int Q, int U, int V) {
    return tree.get(P,U,Q,V);
}

Compilation message (stderr)

game.cpp: In constructor 'node1::node1()':
game.cpp:10:12: warning: 'node1::rc' will be initialized after [-Wreorder]
   10 |     int lc,rc;
      |            ^~
game.cpp:8:15: warning:   'long long int node1::val' [-Wreorder]
    8 |     long long val;
      |               ^~~
game.cpp:11:5: warning:   when initialized here [-Wreorder]
   11 |     node1():lc(0),rc(0),val(0){
      |     ^~~~~

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20