oj.uz

Submission #1025562

# Submission time Handle Problem Language Result Execution time Memory
1025562 2024-07-17T07:02:03 Z socpite Game (IOI13_game) C++
63 / 100
 1079 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 600 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 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 394 ms 50252 KB Output is correct
5 Correct 297 ms 50516 KB Output is correct
6 Correct 400 ms 47400 KB Output is correct
7 Correct 434 ms 47184 KB Output is correct
8 Correct 295 ms 28784 KB Output is correct
9 Correct 421 ms 47440 KB Output is correct
10 Correct 392 ms 47016 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 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 604 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 652 ms 18600 KB Output is correct
13 Correct 804 ms 8960 KB Output is correct
14 Correct 247 ms 1104 KB Output is correct
15 Correct 912 ms 13676 KB Output is correct
16 Correct 228 ms 23408 KB Output is correct
17 Correct 704 ms 16212 KB Output is correct
18 Correct 1056 ms 23772 KB Output is correct
19 Correct 925 ms 23800 KB Output is correct
20 Correct 841 ms 23228 KB Output is correct
21 Correct 1 ms 348 KB Output is correct

Subtask #4
0 / 17.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 344 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 604 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 421 ms 50440 KB Output is correct
13 Correct 302 ms 50520 KB Output is correct
14 Correct 429 ms 47444 KB Output is correct
15 Correct 416 ms 47188 KB Output is correct
16 Correct 309 ms 28776 KB Output is correct
17 Correct 452 ms 47440 KB Output is correct
18 Correct 409 ms 46936 KB Output is correct
19 Correct 622 ms 18952 KB Output is correct
20 Correct 792 ms 8988 KB Output is correct
21 Correct 246 ms 1124 KB Output is correct
22 Correct 889 ms 13540 KB Output is correct
23 Correct 240 ms 23288 KB Output is correct
24 Correct 684 ms 16184 KB Output is correct
25 Correct 986 ms 23696 KB Output is correct
26 Correct 996 ms 23808 KB Output is correct
27 Correct 929 ms 23380 KB Output is correct
28 Correct 549 ms 256000 KB Output is correct
29 Runtime error 988 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 348 KB Output is correct
2 Correct 2 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 2 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 419 ms 50320 KB Output is correct
13 Correct 311 ms 50512 KB Output is correct
14 Correct 432 ms 47440 KB Output is correct
15 Correct 465 ms 47452 KB Output is correct
16 Correct 317 ms 28736 KB Output is correct
17 Correct 454 ms 47432 KB Output is correct
18 Correct 413 ms 46928 KB Output is correct
19 Correct 659 ms 18512 KB Output is correct
20 Correct 812 ms 9004 KB Output is correct
21 Correct 245 ms 1108 KB Output is correct
22 Correct 924 ms 13600 KB Output is correct
23 Correct 236 ms 23376 KB Output is correct
24 Correct 751 ms 16328 KB Output is correct
25 Correct 1079 ms 23548 KB Output is correct
26 Correct 1002 ms 23916 KB Output is correct
27 Correct 976 ms 23284 KB Output is correct
28 Correct 587 ms 256000 KB Output is correct
29 Runtime error 1076 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -