oj.uz

Submission #99196

# Submission time Handle Problem Language Result Execution time Memory
99196 2019-03-01T15:36:53 Z maruii Game (IOI13_game) C++14
80 / 100
 6631 ms 257024 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int R, C;
struct ST{
    struct Node{
        int l=0, r=0;
        ll v=0;
    };
    vector<Node> node;
    void update(int nn, int ns, int ne, int x, ll v){
        if(ns>x || ne<x) return;
        if(ns==ne){
            node[nn].v = v;
            return;
        }
        int m = ns+ne>>1;
        if(m<x){
            if(!node[nn].r) node[nn].r = node.size(), node.resize(node[nn].r+1);
            update(node[nn].r, m+1, ne, x, v);
        }
        else{
            if(!node[nn].l) node[nn].l = node.size(), node.resize(node[nn].l+1);
            update(node[nn].l, ns, m, x, v);
        }
        node[nn].v = __gcd(node[nn].l?node[node[nn].l].v:0ll, node[nn].r?node[node[nn].r].v:0ll);
    }
    ll query(int nn, int ns, int ne, int s, int e){
        if(ns>e || ne<s) return 0;
        if(s<=ns && ne<=e) return node[nn].v;
        int m = ns+ne>>1;
        return __gcd(node[nn].l?query(node[nn].l, ns, m, s, e):0ll, node[nn].r?query(node[nn].r, m+1, ne, s, e):0ll);
    }
};

struct ST2{
    struct Node{
        int l=0, r=0;
        ST v;
    };
    vector<Node> node;
    void update(int nn, int ns, int ne, int x, int xx, ll v){
        if(ns>x || ne<x) return;
        if(ns==ne){
            node[nn].v.update(0, 0, C, xx, v);
            return;
        }
        int m = ns+ne>>1;
        if(m<x){
            if(!node[nn].r) node[nn].r = node.size(), node.resize(node[nn].r+1), node[node[nn].r].v.node.resize(1);
            update(node[nn].r, m+1, ne, x, xx, v);
        }
        else{
            if(!node[nn].l) node[nn].l = node.size(), node.resize(node[nn].l+1), node[node[nn].l].v.node.resize(1);
            update(node[nn].l, ns, m, x, xx, v);
        }
        node[nn].v.update(0, 0, C, xx, __gcd(node[nn].l?node[node[nn].l].v.query(0, 0, C, xx, xx):0ll, node[nn].r?node[node[nn].r].v.query(0, 0, C, xx, xx):0ll));
    }
    ll query(int nn, int ns, int ne, int s, int e, int ss, int ee){
        if(ns>e || ne<s) return 0;
        if(s<=ns && ne<=e) return node[nn].v.query(0, 0, C, ss, ee);
        int m = ns+ne>>1;
        return __gcd(node[nn].l?query(node[nn].l, ns, m, s, e, ss, ee):0ll, node[nn].r?query(node[nn].r, m+1, ne, s, e, ss, ee):0ll);
    }
} seg;

void init(int R_, int C_) {
    R = R_ - 1, C = C_ - 1;
    seg.node.resize(1);
    seg.node[0].v.node.resize(1);
}

void update(int P, int Q, ll K) {
    seg.update(0, 0, R, P, Q, K);
}

ll calculate(int P, int Q, int U, int V) {
    return seg.query(0, 0, R, P, U, Q, V);
}

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 member function 'void ST::update(int, int, int, int, ll)':
game.cpp:18:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = ns+ne>>1;
                 ~~^~~
game.cpp: In member function 'll ST::query(int, int, int, int, int)':
game.cpp:32:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = ns+ne>>1;
                 ~~^~~
game.cpp: In member function 'void ST2::update(int, int, int, int, int, ll)':
game.cpp:49:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = ns+ne>>1;
                 ~~^~~
game.cpp: In member function 'll ST2::query(int, int, int, int, int, int, int)':
game.cpp:63:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = ns+ne>>1;
                 ~~^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 256 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 4 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 900 ms 12376 KB Output is correct
5 Correct 790 ms 12620 KB Output is correct
6 Correct 857 ms 9232 KB Output is correct
7 Correct 974 ms 9336 KB Output is correct
8 Correct 541 ms 7400 KB Output is correct
9 Correct 925 ms 9268 KB Output is correct
10 Correct 999 ms 8240 KB Output is correct
11 Correct 2 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 4 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 252 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 9 ms 384 KB Output is correct
12 Correct 1764 ms 14940 KB Output is correct
13 Correct 2885 ms 7092 KB Output is correct
14 Correct 405 ms 3388 KB Output is correct
15 Correct 3340 ms 8708 KB Output is correct
16 Correct 421 ms 15736 KB Output is correct
17 Correct 1339 ms 11368 KB Output is correct
18 Correct 2674 ms 16924 KB Output is correct
19 Correct 2234 ms 19256 KB Output is correct
20 Correct 2139 ms 18652 KB Output is correct
21 Correct 2 ms 256 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 3 ms 256 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 979 ms 12224 KB Output is correct
13 Correct 686 ms 12416 KB Output is correct
14 Correct 827 ms 9160 KB Output is correct
15 Correct 918 ms 8928 KB Output is correct
16 Correct 641 ms 7320 KB Output is correct
17 Correct 989 ms 9208 KB Output is correct
18 Correct 752 ms 8268 KB Output is correct
19 Correct 1564 ms 15096 KB Output is correct
20 Correct 2659 ms 6896 KB Output is correct
21 Correct 466 ms 3192 KB Output is correct
22 Correct 3231 ms 8584 KB Output is correct
23 Correct 351 ms 15828 KB Output is correct
24 Correct 1352 ms 11260 KB Output is correct
25 Correct 2841 ms 16944 KB Output is correct
26 Correct 2323 ms 19444 KB Output is correct
27 Correct 2105 ms 18756 KB Output is correct
28 Correct 1300 ms 157292 KB Output is correct
29 Correct 2999 ms 172656 KB Output is correct
30 Correct 6488 ms 124488 KB Output is correct
31 Correct 6108 ms 101692 KB Output is correct
32 Correct 805 ms 10360 KB Output is correct
33 Correct 1065 ms 12664 KB Output is correct
34 Correct 1066 ms 166808 KB Output is correct
35 Correct 2303 ms 91284 KB Output is correct
36 Correct 4492 ms 170616 KB Output is correct
37 Correct 3563 ms 170884 KB Output is correct
38 Correct 3732 ms 170368 KB Output is correct
39 Correct 3338 ms 133880 KB Output is correct
40 Correct 2 ms 256 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 4 ms 384 KB Output is correct
4 Correct 4 ms 512 KB Output is correct
5 Correct 3 ms 256 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 256 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 2 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 859 ms 12124 KB Output is correct
13 Correct 568 ms 12596 KB Output is correct
14 Correct 742 ms 9168 KB Output is correct
15 Correct 1090 ms 9084 KB Output is correct
16 Correct 820 ms 7380 KB Output is correct
17 Correct 718 ms 9180 KB Output is correct
18 Correct 761 ms 8276 KB Output is correct
19 Correct 1379 ms 15068 KB Output is correct
20 Correct 2904 ms 7196 KB Output is correct
21 Correct 377 ms 3320 KB Output is correct
22 Correct 3191 ms 8576 KB Output is correct
23 Correct 344 ms 15812 KB Output is correct
24 Correct 1425 ms 11164 KB Output is correct
25 Correct 2479 ms 17792 KB Output is correct
26 Correct 2240 ms 19320 KB Output is correct
27 Correct 2202 ms 18584 KB Output is correct
28 Correct 1488 ms 157356 KB Output is correct
29 Correct 3376 ms 172612 KB Output is correct
30 Correct 6631 ms 124628 KB Output is correct
31 Correct 6133 ms 101860 KB Output is correct
32 Correct 669 ms 10488 KB Output is correct
33 Correct 1086 ms 12824 KB Output is correct
34 Correct 1012 ms 166796 KB Output is correct
35 Correct 2566 ms 91456 KB Output is correct
36 Correct 4784 ms 170752 KB Output is correct
37 Correct 3967 ms 170860 KB Output is correct
38 Correct 3780 ms 170440 KB Output is correct
39 Runtime error 1640 ms 257024 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -