oj.uz

Submission #364454

# Submission time Handle Problem Language Result Execution time Memory
364454 2021-02-09T08:24:59 Z thanksone Game (IOI13_game) C++14
100 / 100
 4041 ms 171176 KB 
#include <game.h>
#include <bits/stdc++.h>
#define ff first
#define ss second
#define mid (l + r) / 2
using namespace std;
int R, C;
long long gcd(long long a, long long b){
    if(!b) return a;
    if(!a) return b;
    return gcd(b, a % b);
}
struct segleaf{
    long long val;
    pair<long long, int> tag;
    segleaf *lc, *rc;
    segleaf(){lc = rc = nullptr, val = 0, tag = {0, 0};}
    segleaf(long long v, int y){lc = rc = nullptr, val = v, tag = {v, y};}
    inline void pull(){
        val = gcd((lc? lc->val : 0), (rc? rc->val : 0));
    }
    inline void push(int m){
        if(tag.ff){
            if(tag.ss <= m) lc = new segleaf(tag.ff, tag.ss);
            else rc = new segleaf(tag.ff, tag.ss);
            tag = {0, 0};
        }
    }
    void update(int y, int l, int r, long long v){
        if(y == l && y == r){
            val = v;
            return;
        }
        push(mid);
        if(y <= mid){
            if(!lc)lc = new segleaf(v, y);
            else lc->update(y, l, mid, v);
        }else{
            if(!rc) rc = new segleaf(v, y);
            else rc->update(y, mid + 1, r, v);
        }
        pull();
    }
    long long query(int up, int down, int l, int r){
        if(tag.ff){
            if(tag.ss >= up && tag.ss <= down) return val;
            else return 0;
        }
        if(up == l && down == r) return val;
        push(mid);
        if(down <= mid) return (lc? lc->query(up, down, l, mid) : 0);
        else if(up > mid) return (rc? rc->query(up, down, mid + 1, r) : 0);
        else return gcd((lc? lc->query(up, mid, l, mid) : 0), (rc? rc->query(mid + 1, down, mid + 1, r) : 0));
    }
};
struct segtree{
    segleaf s;
    segtree *lc, *rc;
    segtree(){lc = rc = nullptr;}
    inline void pull(int y){
        s.update(y, 0, C - 1, gcd((lc? lc->s.query(y, y, 0, C - 1) : 0), (rc? rc->s.query(y, y, 0, C - 1) :0)));
    }
    void update(int x, int y, int l, int r, long long v){
        if(x == l && x == r){
            s.update(y, 0, C - 1, v);
            return;
        }
        if(x <= mid){
            if(!lc) lc = new segtree;
            lc->update(x, y, l, mid, v);
        }else{
            if(!rc) rc = new segtree;
            rc->update(x, y, mid + 1, r, v);
        }
        pull(y);
    }
    long long query(int left, int right, int up, int down, int l, int r){
        if(left == l && right == r) return s.query(up, down, 0, C - 1);
        else if(right <= mid) return (lc? lc->query(left, right, up, down, l, mid) : 0);
        else if(left > mid) return (rc? rc->query(left, right, up, down, mid + 1, r) : 0);
        else return gcd((lc? lc->query(left, mid, up, down, l, mid) : 0), (rc? rc->query(mid + 1, right, up, down, mid + 1, r) : 0));
    }
}root;
void init(int r, int c){
    R = r;
    C = c;
}
void update(int p, int q, long long k){
    root.update(p, q, 0, R - 1, k);
}
long long calculate(int l, int u, int r, int d){
    return root.query(l, r, u, d, 0, R - 1);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 504 ms 13804 KB Output is correct
5 Correct 394 ms 13728 KB Output is correct
6 Correct 424 ms 10988 KB Output is correct
7 Correct 513 ms 10916 KB Output is correct
8 Correct 319 ms 8708 KB Output is correct
9 Correct 464 ms 10988 KB Output is correct
10 Correct 439 ms 10636 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 849 ms 17132 KB Output is correct
13 Correct 1434 ms 10932 KB Output is correct
14 Correct 279 ms 5740 KB Output is correct
15 Correct 1693 ms 13640 KB Output is correct
16 Correct 212 ms 15852 KB Output is correct
17 Correct 699 ms 12124 KB Output is correct
18 Correct 1314 ms 17516 KB Output is correct
19 Correct 1098 ms 17392 KB Output is correct
20 Correct 1012 ms 16876 KB Output is correct
21 Correct 1 ms 364 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 502 ms 13800 KB Output is correct
13 Correct 400 ms 13548 KB Output is correct
14 Correct 422 ms 11000 KB Output is correct
15 Correct 480 ms 10860 KB Output is correct
16 Correct 323 ms 8556 KB Output is correct
17 Correct 463 ms 10732 KB Output is correct
18 Correct 464 ms 10608 KB Output is correct
19 Correct 860 ms 17004 KB Output is correct
20 Correct 1386 ms 10732 KB Output is correct
21 Correct 284 ms 5740 KB Output is correct
22 Correct 1602 ms 13348 KB Output is correct
23 Correct 220 ms 15852 KB Output is correct
24 Correct 672 ms 12012 KB Output is correct
25 Correct 1293 ms 17384 KB Output is correct
26 Correct 1085 ms 17388 KB Output is correct
27 Correct 1027 ms 16876 KB Output is correct
28 Correct 571 ms 53356 KB Output is correct
29 Correct 1294 ms 48644 KB Output is correct
30 Correct 3147 ms 46772 KB Output is correct
31 Correct 2930 ms 86508 KB Output is correct
32 Correct 460 ms 10696 KB Output is correct
33 Correct 621 ms 14572 KB Output is correct
34 Correct 282 ms 41964 KB Output is correct
35 Correct 924 ms 28604 KB Output is correct
36 Correct 1907 ms 46448 KB Output is correct
37 Correct 1407 ms 46444 KB Output is correct
38 Correct 1383 ms 45912 KB Output is correct
39 Correct 1172 ms 37996 KB Output is correct
40 Correct 1 ms 364 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 499 ms 13676 KB Output is correct
13 Correct 402 ms 13548 KB Output is correct
14 Correct 446 ms 10988 KB Output is correct
15 Correct 491 ms 10752 KB Output is correct
16 Correct 321 ms 8684 KB Output is correct
17 Correct 487 ms 10732 KB Output is correct
18 Correct 440 ms 10476 KB Output is correct
19 Correct 858 ms 17056 KB Output is correct
20 Correct 1413 ms 10604 KB Output is correct
21 Correct 279 ms 5924 KB Output is correct
22 Correct 1627 ms 13404 KB Output is correct
23 Correct 210 ms 15852 KB Output is correct
24 Correct 685 ms 12012 KB Output is correct
25 Correct 1264 ms 17424 KB Output is correct
26 Correct 1040 ms 17388 KB Output is correct
27 Correct 959 ms 17008 KB Output is correct
28 Correct 537 ms 53352 KB Output is correct
29 Correct 1294 ms 48440 KB Output is correct
30 Correct 3094 ms 46596 KB Output is correct
31 Correct 2980 ms 86692 KB Output is correct
32 Correct 457 ms 10800 KB Output is correct
33 Correct 623 ms 14444 KB Output is correct
34 Correct 281 ms 42092 KB Output is correct
35 Correct 884 ms 28268 KB Output is correct
36 Correct 1868 ms 46376 KB Output is correct
37 Correct 1445 ms 46572 KB Output is correct
38 Correct 1388 ms 45968 KB Output is correct
39 Correct 726 ms 105196 KB Output is correct
40 Correct 2153 ms 89380 KB Output is correct
41 Correct 4041 ms 92412 KB Output is correct
42 Correct 3953 ms 171176 KB Output is correct
43 Correct 490 ms 83808 KB Output is correct
44 Correct 612 ms 11120 KB Output is correct
45 Correct 1198 ms 37868 KB Output is correct
46 Correct 2405 ms 88060 KB Output is correct
47 Correct 2414 ms 87820 KB Output is correct
48 Correct 2312 ms 87504 KB Output is correct
49 Correct 1 ms 492 KB Output is correct