제출 #282070

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
282070		rqi	게임 (IOI13_game)	C++14	100 / 100	3929 ms	93804 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef long double ld;

#define f first
#define s second
#define mp make_pair
#define bk back()
#define pb push_back

const ld PI = acos((ld)-1);
int MAXX = 1000000000;
int MAXY = 1000000000;

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

pi getRang(pi a, int b, int L = 0, int R = MAXY-1){
    if(L > a.f || a.s > R || L > b || b > R) return mp(-1, -1);
    int M = (L+R)/2;
    pi res1 = getRang(a, b, L, M);
    if(res1 != mp(-1, -1)) return res1;
    pi res2 = getRang(a, b, M+1, R);
    if(res2 != mp(-1, -1)) return res2;
    return mp(L, R);
}

struct Node{
    int L, R, M;
    ll val;
    Node* c[2];

    Node(int _L, int _R, ll _val = 0){
        L = _L;
        R = _R;
        M = (L+R)/2;
        val = _val;
    }

    void pull(){
        val = 0;
        if(c[0]) val = gcd2(val, c[0]->val);
        if(c[1]) val = gcd2(val, c[1]->val);
    }

    void upd(int pos, ll inc){ 
        assert(L <= pos && pos <= R);
        if(L == R){
            val = inc;
            return;
        }
        
        if(pos <= M){
            if(!c[0]){
                c[0] = new Node(pos, pos, inc);
            }
            else{
                if(c[0]->L <= pos && pos <= c[0]->R){
                    c[0]->upd(pos, inc);
                }
                else{
                    pi rang = getRang(mp(c[0]->L, c[0]->R), pos);
                    if(c[0]->R < pos){
                        Node* par = new Node(rang.f, rang.s);
                        par->c[0] = c[0];
                        par->c[1] = new Node(pos, pos, inc);
                        c[0] = par;
                        par->pull();
                    }
                    else{
                        Node* par = new Node(rang.f, rang.s);
                        par->c[1] = c[0];
                        par->c[0] = new Node(pos, pos, inc);
                        c[0] = par;
                        par->pull();
                    }
                }
            }
        }
        else{
            if(!c[1]){
                c[1] = new Node(pos, pos, inc);
            }
            else{
                if(c[1]->L <= pos && pos <= c[1]->R){
                    c[1]->upd(pos, inc);
                }
                else{
                    pi rang = getRang(mp(c[1]->L, c[1]->R), pos);
                    if(c[1]->R < pos){
                        Node* par = new Node(rang.f, rang.s);
                        par->c[0] = c[1];
                        par->c[1] = new Node(pos, pos, inc);
                        c[1] = par;
                        par->pull();
                    }
                    else{
                        Node* par = new Node(rang.f, rang.s);
                        par->c[1] = c[1];
                        par->c[0] = new Node(pos, pos, inc);
                        c[1] = par;
                        par->pull();
                    }
                }
            }
        }
        //cout << "L, R, val, pos, inc: " << L << " " << R << " " << val << " " << pos << " " << inc << "\n";
        // if(c[0]){
        //     cout << "c[0]->L, R, val: " << c[0]->L << " " << c[0]->R << " " << c[0]->val << "\n";
        // }
        // if(c[1]){
        //     cout << "c[1]->L, R, val: " << c[1]->L << " " << c[1]->R << " " << c[1]->val << "\n";
        // }
        pull();
        //cout << "L, R, val, pos, inc: " << L << " " << R << " " << val << " " << pos << " " << inc << "\n";
    }

    ll query(int lo, int hi){
        if(R < lo || hi < L) return 0;
        if(lo <= L && R <= hi){
            return val;
        }
        ll res = 0;
        if(c[0]){
            res = gcd2(res, c[0]->query(lo, hi));
        }
        if(c[1]){
            res = gcd2(res, c[1]->query(lo, hi));
        }
        return res;
    }
};

struct Sparse{
    int L, R, M;
    Node* seg;
    Sparse* c[2];

    Sparse(int _L, int _R){
        L = _L;
        R = _R;
        M = (L+R)/2;
        seg = new Node(0, MAXY-1, 0);
    }



    void upd(int x, int y, ll inc){
        if(x < L || R < x) return;
        //cout << "L, R, x, y, inc: " << L << " " << R << " " << x << " " << y << " " << inc << "\n";
        //cout << "seg->query(0, 1): " << seg->query(0, 1) << "\n";
        //seg->upd(y, inc);
        //cout << "seg->query(0, 1): " << seg->query(0, 1) << "\n";
        if(L == R){
            seg->upd(y, inc);
            return;
        }
        if(x <= M){
            if(!c[0]) c[0] = new Sparse(L, M);
            c[0]->upd(x, y, inc);
        }
        else{
            if(!c[1]) c[1] = new Sparse(M+1, R);
            c[1]->upd(x, y, inc);
        }
        ll val = 0;
        if(c[0]) val = gcd2(val, c[0]->seg->query(y, y));
        if(c[1]) val = gcd2(val, c[1]->seg->query(y, y));
        seg->upd(y, val);
    }

    ll query(int lox, int hix, int loy, int hiy){
        if(R < lox || hix < L) return 0;
        if(lox <= L && R <= hix){
            return seg->query(loy, hiy);
        }
        ll res = 0;
        if(c[0]){
            res = gcd2(res, c[0]->query(lox, hix, loy, hiy));
        }
        if(c[1]){
            res = gcd2(res, c[1]->query(lox, hix, loy, hiy));
        }
        return res;
    }
    
};

// bool check(pi a){
//     if(a.f < 0 || a.f > MAXX) return 0;
//     if(a.s < 0 || a.s > MAXY) return 0;
//     return 1;
// }

Sparse* seg;

void init(int R, int C) {
    MAXX = R;
    MAXY = C;
    // pi test = getRang(mp(1, 1), 2);
    // cout << test.f << " " << test.s << "\n";
    seg = new Sparse(0, MAXX-1);
}

void update(int P, int Q, long long K) {
    //cout << "UPDATE " << P << " " << Q << " " << K << "\n";
    seg->upd(P, Q, K);
    // vpi x, y;
    // x.pb(mp(P, P)); y.pb(mp(Q, Q));
    // int curb = 0;
    // while(true){
    //     pi newx = x.bk;
    //     if((((newx.f)>>curb)&1) == 1){
    //         newx.f-=(1<<curb);
    //     }
    //     if((((newx.s)>>curb)&1) == 0){
    //         newx.s+=(1<<curb);
    //     }
    //     if(check(newx)){
    //         x.pb(newx);
    //     }
    //     else break;
    //     curb++;
    //     // cout << newx.f << " " << newx.s << "\n";
    //     // cout << "HI\n";
    //     // cout.flush();
    // }
    // curb = 0;
    // while(true){
    //     pi newy = y.bk;
    //     if((((newy.f)>>curb)&1) == 1){
    //         newy.f-=(1<<curb);
    //     }
    //     if((((newy.s)>>curb)&1) == 0){
    //         newy.s+=(1<<curb);
    //     }
    //     if(check(newy)){
    //         y.pb(newy);
    //     }
    //     else break;
    //     curb++;
        
    // }
    // for(auto a: x){
    //     for(auto b: y){
    //         seg[mp(a, b)] = gcd2(seg[mp(a, b)], K);
    //     }
    // }
}

ll calculate(int lox, int loy, int hix, int hiy) {
    //cout << "QUERY " << lox << " " << hix << " " << loy << " " << hiy << "\n";
    return seg->query(lox, hix, loy, hiy);
    // //cout << "calculate " << P << " " << Q << " " << U << " " << V << "\n";
    // vpi x, y;
    // pi curx = mp(P, U);
    // pi cury = mp(Q, V);
    // int curb = 0;
    // while(curx.f <= curx.s){
    //     if(((curx.f>>curb)&1) == 1){
    //         x.pb(mp(curx.f, curx.f+(1<<curb)-1));
    //         curx.f+=(1<<curb);
    //     }
    //     if(curx.f > curx.s) break;
    //     if(((curx.s>>curb)&1) == 0){
    //         x.pb(mp(curx.s-(1<<curb)+1, curx.s));
    //         curx.s-=(1<<curb);
    //     }
    //     curb++;
    // }
    // curb = 0;
    // while(cury.f <= cury.s){
    //     if(((cury.f>>curb)&1) == 1){
    //         y.pb(mp(cury.f, cury.f+(1<<curb)-1));
    //         cury.f+=(1<<curb);
    //     }
    //     if(cury.f > cury.s) break;
    //     if(((cury.s>>curb)&1) == 0){
    //         y.pb(mp(cury.s-(1<<curb)+1, cury.s));
    //         cury.s-=(1<<curb);
    //     }
    //     curb++;
    // }

    // ll res = 0;
    // // for(auto u: x){
    // //     cout << u.f << " " << u.s << "\n";
    // // }
    // // cout << "\n";
    // // for(auto u: y){
    // //     cout << u.f << " " << u.s << "\n";
    // // }
    // for(auto a: x){
    //     for(auto b: y){
    //         if(seg.count(mp(a, b))) res = gcd2(res, seg[mp(a, b)]);
    //     }
    // }
    // /* ... */
    // return res;
}

컴파일 시 표준 에러 (stderr) 메시지

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   18 |  int res;
      |      ^~~

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