oj.uz

Submission #1025559

# Submission time Handle Problem Language Result Execution time Memory
1025559 2024-07-17T06:59:31 Z socpite Game (IOI13_game) C++17
63 / 100
 1071 ms 256000 KB 
#include <bits/stdc++.h>
using namespace std;

#include "game.h"

const int maxn = 1e9;

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;
}

struct st1d{
    st1d *lc, *rc;
    long long val;
    st1d(): val(0), lc(nullptr), rc(nullptr){}
    void add(int y, long long p, int l = 0, int r = maxn){
        if(l == r){
            val = p;
            return;
        }
        int mid = (l+r)>>1;
        if(y <= mid){
            if(!lc)lc = new st1d();
            lc->add(y, p, l, mid);
            if(rc)val = gcd2(lc->val, rc->val);
            else val = lc->val;
        }
        else {
            if(!rc)rc = new st1d();
            rc->add(y, p, mid+1, r);
            if(lc)val = gcd2(lc->val, rc->val);
            else val = rc->val;
        }
    }
    void cpy(st1d &b, int y, int l = 0, int r = maxn){
        val = b.val;
        if(l == r)return;
        int mid = (l+r)>>1;
        if(y <= mid){
            if(!lc)lc = new st1d();
            lc->cpy(*b.lc, y, l, mid);
        }
        else {
            if(!rc)rc = new st1d();
            rc->cpy(*b.rc, y, mid+1, r);
        }
    }
    void merge(st1d &bl, st1d &br, int y, int l = 0, int r = maxn){
        val = gcd2(bl.val, br.val);
        if(l == r)return;
        int mid = (l+r)>>1;
        if(y <= mid){
            if(!lc)lc = new st1d();
            if(!bl.lc)lc->cpy(*br.lc, y, l, mid);
            else if(!br.lc)lc->cpy(*bl.lc, y, l, mid);
            else lc->merge(*bl.lc, *br.lc, y, l, mid);
            
        }
        else {
            if(!rc)rc = new st1d();
            if(!bl.rc)rc->cpy(*br.rc, y, mid+1, r);
            else if(!br.rc)rc->cpy(*bl.rc, y, mid+1, r);
            else rc->merge(*bl.rc, *br.rc, y, mid+1, r);
        }
    }
    long long query(int ql, int qr, int l = 0, int r = maxn){
        if(ql > r || l > qr)return 0;
        if(ql <= l && r <= qr)return val;
        int mid = (l+r)>>1;
        long long lhs = lc ? lc->query(ql, qr, l, mid) : 0, rhs = rc ? rc->query(ql, qr, mid+1, r) : 0;
        return gcd2(lhs, rhs);
    }
};

struct st2d{
    st2d *lc, *rc;
    int l, r;
    st1d st;
    st2d(int _l, int _r): st(), l(_l), r(_r), lc(nullptr), rc(nullptr){}
    void add(int x, int y, long long p){
        if(l == r){
            st.add(y, p);
            return;
        }
        int mid = (l+r)>>1;
        if(x <= mid){
            if(!lc)lc = new st2d(l, mid);
            lc->add(x, y, p);
            if(rc)st.merge(lc->st, rc->st, y);
            else st.cpy(lc->st, y);
        }
        else {
            if(!rc)rc = new st2d(mid+1, r);
            rc->add(x, y, p);
            if(lc)st.merge(lc->st, rc->st, y);
            else st.cpy(rc->st, y);
        }
    }
    long long query(int p, int q, int u, int v){
        if(l > u || r < p)return 0;
        if(p <= l && r <= u)return st.query(q, v);
        long long lhs = lc ? lc->query(p, q, u, v) : 0, rhs = rc ? rc->query(p, q, u, v) : 0;
        return gcd2(lhs, rhs);
    }

}rt(0, maxn);

void init(int R, int C) {
    
}

void update(int P, int Q, long long K) {
    rt.add(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    /* ... */
    return rt.query(P, Q, U, V);
}

Compilation message

game.cpp: In constructor 'st1d::st1d()':
game.cpp:20:15: warning: 'st1d::val' will be initialized after [-Wreorder]
   20 |     long long val;
      |               ^~~
game.cpp:19:11: warning:   'st1d* st1d::lc' [-Wreorder]
   19 |     st1d *lc, *rc;
      |           ^~
game.cpp:21:5: warning:   when initialized here [-Wreorder]
   21 |     st1d(): val(0), lc(nullptr), rc(nullptr){}
      |     ^~~~
game.cpp: In constructor 'st2d::st2d(int, int)':
game.cpp:84:10: warning: 'st2d::st' will be initialized after [-Wreorder]
   84 |     st1d st;
      |          ^~
game.cpp:83:9: warning:   'int st2d::l' [-Wreorder]
   83 |     int l, r;
      |         ^
game.cpp:85:5: warning:   when initialized here [-Wreorder]
   85 |     st2d(int _l, int _r): st(), l(_l), r(_r), lc(nullptr), rc(nullptr){}
      |     ^~~~
game.cpp:83:12: warning: 'st2d::r' will be initialized after [-Wreorder]
   83 |     int l, r;
      |            ^
game.cpp:82:11: warning:   'st2d* st2d::lc' [-Wreorder]
   82 |     st2d *lc, *rc;
      |           ^~
game.cpp:85:5: warning:   when initialized here [-Wreorder]
   85 |     st2d(int _l, int _r): st(), l(_l), r(_r), lc(nullptr), rc(nullptr){}
      |     ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 407 ms 50300 KB Output is correct
5 Correct 346 ms 50512 KB Output is correct
6 Correct 417 ms 47484 KB Output is correct
7 Correct 422 ms 47184 KB Output is correct
8 Correct 301 ms 28688 KB Output is correct
9 Correct 438 ms 47440 KB Output is correct
10 Correct 407 ms 47028 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 626 ms 18584 KB Output is correct
13 Correct 871 ms 9044 KB Output is correct
14 Correct 268 ms 1272 KB Output is correct
15 Correct 933 ms 13544 KB Output is correct
16 Correct 236 ms 23380 KB Output is correct
17 Correct 739 ms 16212 KB Output is correct
18 Correct 1045 ms 23580 KB Output is correct
19 Correct 922 ms 23892 KB Output is correct
20 Correct 870 ms 23124 KB Output is correct
21 Correct 0 ms 344 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 439 ms 50408 KB Output is correct
13 Correct 319 ms 50516 KB Output is correct
14 Correct 430 ms 47520 KB Output is correct
15 Correct 451 ms 47440 KB Output is correct
16 Correct 296 ms 28848 KB Output is correct
17 Correct 443 ms 47448 KB Output is correct
18 Correct 408 ms 47016 KB Output is correct
19 Correct 619 ms 18512 KB Output is correct
20 Correct 801 ms 8976 KB Output is correct
21 Correct 235 ms 1284 KB Output is correct
22 Correct 885 ms 13392 KB Output is correct
23 Correct 237 ms 23376 KB Output is correct
24 Correct 700 ms 16348 KB Output is correct
25 Correct 1071 ms 23632 KB Output is correct
26 Correct 985 ms 23888 KB Output is correct
27 Correct 904 ms 23124 KB Output is correct
28 Correct 534 ms 256000 KB Output is correct
29 Runtime error 992 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 2 ms 600 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 410 ms 50256 KB Output is correct
13 Correct 304 ms 50516 KB Output is correct
14 Correct 415 ms 47520 KB Output is correct
15 Correct 423 ms 47448 KB Output is correct
16 Correct 310 ms 28752 KB Output is correct
17 Correct 443 ms 47692 KB Output is correct
18 Correct 406 ms 46928 KB Output is correct
19 Correct 625 ms 18728 KB Output is correct
20 Correct 837 ms 8900 KB Output is correct
21 Correct 268 ms 1104 KB Output is correct
22 Correct 875 ms 13508 KB Output is correct
23 Correct 239 ms 23364 KB Output is correct
24 Correct 688 ms 16208 KB Output is correct
25 Correct 1054 ms 23780 KB Output is correct
26 Correct 925 ms 23720 KB Output is correct
27 Correct 865 ms 23304 KB Output is correct
28 Correct 524 ms 256000 KB Output is correct
29 Runtime error 961 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -