oj.uz

Submission #1025553

# Submission time Handle Problem Language Result Execution time Memory
1025553 2024-07-17T06:54:01 Z socpite Game (IOI13_game) C++17
63 / 100
 1294 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;
    int l, r;
    long long val;
    st1d(int _l, int _r): val(0), l(_l), r(_r), lc(nullptr), rc(nullptr){}
    void add(int y, long long p){
        if(l == r){
            val = p;
            return;
        }
        int mid = (l+r)>>1;
        if(y <= mid){
            if(!lc)lc = new st1d(l, mid);
            lc->add(y, p);
            if(rc)val = gcd2(lc->val, rc->val);
            else val = lc->val;
        }
        else {
            if(!rc)rc = new st1d(mid+1, r);
            rc->add(y, p);
            if(lc)val = gcd2(lc->val, rc->val);
            else val = rc->val;
        }
    }
    void cpy(st1d &b, int y){
        val = b.val;
        if(l == r)return;
        int mid = (l+r)>>1;
        if(y <= mid){
            if(!lc)lc = new st1d(l, mid);
            lc->cpy(*b.lc, y);
        }
        else {
            if(!rc)rc = new st1d(mid+1, r);
            rc->cpy(*b.rc, y);
        }
    }
    void merge(st1d &bl, st1d &br, int y){
        val = gcd2(bl.val, br.val);
        if(l == r)return;
        int mid = (l+r)>>1;
        if(y <= mid){
            if(!lc)lc = new st1d(l, mid);
            if(!bl.lc)lc->cpy(*br.lc, y);
            else if(!br.lc)lc->cpy(*bl.lc, y);
            else lc->merge(*bl.lc, *br.lc, y);
            
        }
        else {
            if(!rc)rc = new st1d(mid+1, r);
            if(!bl.rc)rc->cpy(*br.rc, y);
            else if(!br.rc)rc->cpy(*bl.rc, y);
            else rc->merge(*bl.rc, *br.rc, y);
        }
    }
    long long query(int ql, int qr){
        if(ql > r || l > qr)return 0;
        if(ql <= l && r <= qr)return val;
        long long lhs = lc ? lc->query(ql, qr) : 0, rhs = rc ? rc->query(ql, qr) : 0;
        return gcd2(lhs, rhs);
    }
};

struct st2d{
    st2d *lc, *rc;
    int l, r;
    st1d st;
    st2d(int _l, int _r): st(0, maxn), 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(int, int)':
game.cpp:21:15: warning: 'st1d::val' will be initialized after [-Wreorder]
   21 |     long long val;
      |               ^~~
game.cpp:20:9: warning:   'int st1d::l' [-Wreorder]
   20 |     int l, r;
      |         ^
game.cpp:22:5: warning:   when initialized here [-Wreorder]
   22 |     st1d(int _l, int _r): val(0), l(_l), r(_r), lc(nullptr), rc(nullptr){}
      |     ^~~~
game.cpp:20:12: warning: 'st1d::r' will be initialized after [-Wreorder]
   20 |     int l, r;
      |            ^
game.cpp:19:11: warning:   'st1d* st1d::lc' [-Wreorder]
   19 |     st1d *lc, *rc;
      |           ^~
game.cpp:22:5: warning:   when initialized here [-Wreorder]
   22 |     st1d(int _l, int _r): val(0), l(_l), r(_r), 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(0, maxn), 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(0, maxn), l(_l), r(_r), lc(nullptr), rc(nullptr){}
      |     ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 944 KB Output is correct
3 Correct 1 ms 952 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 860 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 860 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 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 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 479 ms 77676 KB Output is correct
5 Correct 328 ms 77232 KB Output is correct
6 Correct 468 ms 75092 KB Output is correct
7 Correct 501 ms 74836 KB Output is correct
8 Correct 341 ms 46416 KB Output is correct
9 Correct 512 ms 75344 KB Output is correct
10 Correct 509 ms 74836 KB Output is correct
11 Correct 1 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 2 ms 860 KB Output is correct
3 Correct 1 ms 860 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 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 748 ms 29972 KB Output is correct
13 Correct 956 ms 16724 KB Output is correct
14 Correct 272 ms 5888 KB Output is correct
15 Correct 1030 ms 24184 KB Output is correct
16 Correct 233 ms 38736 KB Output is correct
17 Correct 825 ms 28376 KB Output is correct
18 Correct 1224 ms 40100 KB Output is correct
19 Correct 1120 ms 40356 KB Output is correct
20 Correct 1062 ms 39632 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 344 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 2 ms 948 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 908 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 506 ms 77768 KB Output is correct
13 Correct 356 ms 77288 KB Output is correct
14 Correct 600 ms 75192 KB Output is correct
15 Correct 600 ms 74936 KB Output is correct
16 Correct 385 ms 46388 KB Output is correct
17 Correct 543 ms 75504 KB Output is correct
18 Correct 504 ms 74832 KB Output is correct
19 Correct 750 ms 29780 KB Output is correct
20 Correct 903 ms 16976 KB Output is correct
21 Correct 261 ms 5972 KB Output is correct
22 Correct 1010 ms 24152 KB Output is correct
23 Correct 235 ms 38516 KB Output is correct
24 Correct 848 ms 28240 KB Output is correct
25 Correct 1294 ms 39964 KB Output is correct
26 Correct 1217 ms 40212 KB Output is correct
27 Correct 1097 ms 39504 KB Output is correct
28 Runtime error 369 ms 256000 KB Execution killed with signal 9
29 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 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 502 ms 77772 KB Output is correct
13 Correct 353 ms 77136 KB Output is correct
14 Correct 505 ms 75060 KB Output is correct
15 Correct 534 ms 74920 KB Output is correct
16 Correct 359 ms 46420 KB Output is correct
17 Correct 522 ms 75344 KB Output is correct
18 Correct 532 ms 74832 KB Output is correct
19 Correct 770 ms 29748 KB Output is correct
20 Correct 951 ms 16740 KB Output is correct
21 Correct 267 ms 6080 KB Output is correct
22 Correct 1008 ms 24148 KB Output is correct
23 Correct 242 ms 38736 KB Output is correct
24 Correct 835 ms 28204 KB Output is correct
25 Correct 1255 ms 39940 KB Output is correct
26 Correct 1098 ms 40068 KB Output is correct
27 Correct 1048 ms 39428 KB Output is correct
28 Runtime error 371 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -