Submission #1075792

#	Time	Username	Problem	Language	Result	Execution time	Memory
1075792		mc061	Game (IOI13_game)	C++17	80 / 100	2439 ms	256000 KiB

game

#pragma once

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

unordered_map<long long, int> big_idx;

const int SZ = 1e9+1;

struct segtree {
    struct smallnode {
        long long ans = 0;
        long long left = -1, right = -1;
    };
    struct bignode {
        long long left = -1, right = -1;
        vector<smallnode> smalls={smallnode()};
        void update(int idx, long long val, int x = 0, int tl = 0, int tr = SZ) {
            if (tl == tr) {
                smalls[x].ans = val;
                return;
            }
            int m = (tl + tr) >> 1;
            if (idx <= m) {
                if (smalls[x].left == -1) {
                    smalls[x].left = smalls.size();
                    smalls.push_back(smallnode());
                }
                update(idx, val, smalls[x].left, tl, m);
            }
            else {
                if (smalls[x].right == -1) {
                    smalls[x].right = smalls.size();
                    smalls.push_back(smallnode());
                }
                update(idx, val, smalls[x].right, m+1, tr);
            }
            smalls[x].ans = (smalls[x].left == -1 ? 0 : smalls[smalls[x].left].ans);
            smalls[x].ans = __gcd(smalls[x].ans, (smalls[x].right == -1 ? 0 : smalls[smalls[x].right].ans));
        }
        long long query(int l, int r, int x = 0, int tl = 0, int tr = SZ) {
            if (tl >= l && tr <= r) return smalls[x].ans;
            if (tr < l || tl > r) return 0;
            int m = (tl + tr) >> 1;
            long long from_r = (smalls[x].right == -1 ? 0 : query(l, r, smalls[x].right, m+1, tr));
            long long from_l = (smalls[x].left == -1 ? 0 : query(l, r, smalls[x].left, tl, m));
            return __gcd(from_l, from_r);
        }
    };
    vector<bignode> bigs={bignode()};

    void update(int i, int j, long long val, int x = 0, int tl = 0, int tr = SZ) {
        if (tl == tr) {
            bigs[x].update(j, val);
            return;
        }
        int m = (tl + tr) >> 1;
        if (i <= m) {
            if (bigs[x].left == -1) {
                bigs[x].left = bigs.size();
                bigs.push_back(bignode());
            }
            update(i, j, val, bigs[x].left, tl, m);
        }
        else {
            if (bigs[x].right == -1) {
                bigs[x].right = bigs.size();
                bigs.push_back(bignode());
            }
            update(i, j, val, bigs[x].right, m+1, tr);
        }
        long long from_l = (bigs[x].left == -1 ? 0 : bigs[bigs[x].left].query(j, j));
        long long from_r = (bigs[x].right == -1 ? 0 : bigs[bigs[x].right].query(j, j));
        bigs[x].update(j, __gcd(from_l, from_r));
    }
    long long query(int l, int r, int jl, int jr, int x = 0, int tl = 0, int tr = SZ) {
        if (tl >= l && tr <= r) {
            return bigs[x].query(jl, jr);
        }
        if (tl > r || l > tr) return 0;
        int m = (tl + tr) >> 1;
        long long from_l = 0;
        long long from_r = 0;
        if (bigs[x].left != -1) from_l = query(l, r, jl, jr, bigs[x].left, tl, m);
        if (bigs[x].right != -1) from_r = query(l, r, jl, jr, bigs[x].right, m+1, tr);
        return __gcd(from_l, from_r);
    }
};

const int SQ = 1e3+1;
segtree now;

void init(int R, int C) {}
void update(int P, int Q, long long K) {
    now.update(P, Q, K);
}
long long calculate(int P, int Q, int U, int V) {
    return now.query(P, U, Q, V);
}

Compilation message (stderr)

game.cpp:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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