oj.uz

Submission #136964

# Submission time Handle Problem Language Result Execution time Memory
136964 2019-07-26T16:58:34 Z Juney Game (IOI13_game) C++14
0 / 100
 160 ms 163960 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

#define MAX_RANGE 1000000000
#define QUERY_SIZE 22000
#define gcd(x, y) __gcd(x, y)

typedef long long ll;

struct CNODE {
    int l, r, data; ll val;
    CNODE() : l(0), r(0), val(0), data(-1) {}
};

int ct_sz = 1;
CNODE CT[QUERY_SIZE * 300];

struct RNODE {
    int l, r, croot;
    int get_root() {
        if(croot == 0) croot = ++ct_sz;
        return croot;
    }
    RNODE() : l(0), r(0), croot(0) {}
};

int rt_sz = 1;
RNODE RT[QUERY_SIZE * 33];

struct CDST {
    void update(int y, ll val, int l, int r, int n) {
        if(l == r) {
            CT[n].val = val;
            return;
        }
        int mid = (l + r) >> 1;
        if(CT[n].data != -1) {
            if(CT[n].data <= mid) {
                CT[n].l = ++ct_sz;
                CT[CT[n].l].data = CT[n].data, CT[CT[n].l].val = CT[n].val;
            }
            else {
                CT[n].r = ++ct_sz;
                CT[CT[n].r].data = CT[n].data, CT[CT[n].r].val = CT[n].val;
            }
            CT[n].data = -1;
        }
        if(y <= mid) {
            if(CT[n].l == 0) {
                CT[n].l = ++ct_sz;
                CT[CT[n].l].data = y, CT[CT[n].l].val = val;
            }
            else update(y, val, l, mid , CT[n].l);
        }
        else {
            if(CT[n].r == 0) {
                CT[n].r = ++ct_sz;
                CT[CT[n].r].data = y, CT[CT[n].r].val = val;
            }
            else update(y, val, mid+1, r, CT[n].r);
        }
        CT[n].val = gcd(CT[CT[n].l].val, CT[CT[n].r].val);
    }
    void update(int y, ll val, int n) { update(y, val, 1, MAX_RANGE, n); }
    ll query(int c1, int c2, int l, int r, int n) {
        if(n == 0 || r < c1 || c2 < l) return 0;
        if(c1 <= l && r <= c2) return CT[n].val;
        if(CT[n].data != -1) {
            if(l <= CT[n].data && CT[n].data <= r) return CT[n].val;
            return 0;
        }
        int mid = (l + r) >> 1;
        return gcd(query(c1, c2, l, mid, CT[n].l), query(c1, c2, mid+1, r, CT[n].r));
    }
    ll query(int c1, int c2, int n) { return query(c1, c2, 1, MAX_RANGE, n); }
} cdst;

struct RDST {
    void update(int x, int y, ll val, int l=1, int r=MAX_RANGE, int n=1) {
        if(l == r) {
            cdst.update(y, val, RT[n].get_root());
            return;
        }
        int mid = (l + r) >> 1;
        if(x <= mid) {
            if(RT[n].l == 0) RT[n].l = ++rt_sz;
            update(x, y, val, l, mid, RT[n].l);
        }
        else {
            if(RT[n].r == 0) RT[n].r = ++rt_sz;
            update(x, y, val, mid+1, r, RT[n].r);
        }
        ll nval = gcd(cdst.query(y, y, RT[RT[n].l].get_root()), cdst.query(y, y, RT[RT[n].r].get_root()));
        cdst.update(y, nval, RT[n].get_root());
    }
    ll query(int r1, int c1, int r2, int c2, int l=1, int r=MAX_RANGE, int n=1) {
        if(n == 0 || r < r1 || r2 < l) return 0;
        if(r1 <= l && r <= r2) return cdst.query(c1, c2, RT[n].get_root());
        int mid = (l + r) >> 1;
        return gcd(query(r1, c1, r2, c2, l, mid, RT[n].l), query(r1, c1, r2, c2, mid+1, r, RT[n].r));
    }
} dst;

void init(int R, int C) {
    /* ... */
}

void update(int P, int Q, long long K) {
    dst.update(P+1, Q+1, K);
}

long long calculate(int P, int Q, int U, int V) {
    return dst.query(P+1, Q+1, U+1, V+1);
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~
game.cpp: In constructor 'CNODE::CNODE()':
game.cpp:12:24: warning: 'CNODE::val' will be initialized after [-Wreorder]
     int l, r, data; ll val;
                        ^~~
game.cpp:12:15: warning:   'int CNODE::data' [-Wreorder]
     int l, r, data; ll val;
               ^~~~
game.cpp:13:5: warning:   when initialized here [-Wreorder]
     CNODE() : l(0), r(0), val(0), data(-1) {}
     ^~~~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 163928 KB Output is correct
2 Incorrect 135 ms 163832 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 163960 KB Output is correct
2 Correct 134 ms 163800 KB Output is correct
3 Incorrect 135 ms 163832 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 163760 KB Output is correct
2 Incorrect 138 ms 163880 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 163836 KB Output is correct
2 Incorrect 149 ms 163828 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 163848 KB Output is correct
2 Incorrect 137 ms 163948 KB Output isn't correct
3 Halted 0 ms 0 KB -