oj.uz

Submission #281942

# Submission time Handle Problem Language Result Execution time Memory
281942 2020-08-23T16:04:27 Z amoo_safar Game (IOI13_game) C++17
100 / 100
 6278 ms 235736 KB 
#include "game.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int Inf = 1e9 + 3;
const int LG = 30;
const int MX = 10010;
const int CNT = 198e5;
//int lc[CNT], rc[CNT]
int la = 1;
ll g[CNT];
int sn[CNT];

int ty;
int GetL(int id){
    ty = sn[id] & 7;
    if(ty == 0) return 0;
    if(ty == 1) return 0;
    if(ty == 2) return id + 1;
    if(ty == 3) return id + 1;
    if(ty == 4) return sn[id] >> 3;
    return -1;
}
int GetR(int id){
    ty = sn[id] & 7;
    if(ty == 0) return 0;
    if(ty == 1) return id + 1;
    if(ty == 2) return 0;
    if(ty == 3) return sn[id] >> 3;
    if(ty == 4) return id + 1;
    return -1;
}
void AddL(int id){
    ty = sn[id] & 7;
    if(ty >= 2) assert(false);
    if(ty == 0) ++la, sn[id] = 2;
    else sn[id] = 4 + (++ la) * 8;
}
void AddR(int id){
    ty = sn[id] & 7;
    if(ty == 1 || ty == 3 || ty == 4) assert(false);
    if(ty == 0) ++la, sn[id] = 1;
    else sn[id] = 3 + (++ la) * 8;
}

void Set(int id, int idx, ll val, int L, int R){
    if(L + 1 == R){
        g[id] = val;
        return ;
    }
    int mid = (L + R) >> 1;
    if(idx < mid){
        if(!GetL(id)) AddL(id); //lc[id] = ++la;
        Set(GetL(id), idx, val, L, mid);
    } else {
        if(!GetR(id)) AddR(id); //rc[id] = ++la;
        Set(GetR(id), idx, val, mid, R);
    }
    g[id] = __gcd(g[GetL(id)], g[GetR(id)]);
}

ll Get(int id, int l, int r, int L, int R){
    if(r <= L || R <= l) return 0;
    if(l <= L && R <= r) return g[id];
    int mid = (L + R) >> 1;
    return __gcd(GetL(id) ? Get(GetL(id), l, r, L, mid) : 0, GetR(id) ? Get(GetR(id), l, r, mid, R) : 0);
}

void Update(int id, int hl, int hr, int idx, int L, int R){
    if(L + 1 == R){
        g[id] = __gcd(g[hl], g[hr]);
        return ;
    }
    int mid = (L + R) >> 1;
    if(idx < mid){
        if(!GetL(id)) AddL(id);//lc[id] = ++la;
        Update(GetL(id), GetL(hl), GetL(hr), idx, L, mid);
    } else {
        if(!GetR(id)) AddR(id);//rc[id] = ++la;
        Update(GetR(id), GetR(hl), GetR(hr), idx, mid, R);
    }
    g[id] = __gcd(g[GetL(id)], g[GetR(id)]);
}

//Seg node[MX * LOG];

struct Seg2D {
    int ds;
    Seg2D *Lc, *Rc;
    Seg2D (){
        ds = 0;
        Lc = NULL;
        Rc = NULL;
    }
    void Set2D(int x, int y, ll val, int L, int R){
        if(L + 1 == R){
            if(!ds) ds = ++la;
            Set(ds, y, val, 0, Inf);
            return ;
        }
        int mid = (L + R) >> 1;
        if(x < mid){
            if(!Lc) Lc = new Seg2D();
            Lc -> Set2D(x, y, val, L, mid);
        } else {
            if(!Rc) Rc = new Seg2D();
            Rc -> Set2D(x, y, val, mid, R);
        }
        if(!ds) ds = ++la;
        Update(ds, Lc ? Lc -> ds : 0, Rc ? Rc -> ds : 0, y, 0, Inf);
    }
    ll Get2D(int lx, int rx, int ly, int ry, int L, int R){
        if(rx <= L || R <= lx) return 0;
        if(lx <= L && R <= rx){
            if(ds == 0) return 0;
            return Get(ds, ly, ry, 0, Inf);
        }
        int mid = (L + R) >> 1;
        return __gcd(Lc ? Lc -> Get2D(lx, rx, ly, ry, L, mid) : 0, Rc ? Rc -> Get2D(lx, rx, ly, ry, mid, R) : 0);
    }
};
Seg2D Board;

void init(int R, int C) {
    assert(R <= Inf);
    assert(C <= Inf);
}

void update(int P, int Q, ll K) {
    Board.Set2D(P, Q, K, 0, Inf);
}

ll calculate(int P, int Q, int U, int V) {
    return Board.Get2D(P, U + 1, Q, V + 1, 0, Inf);
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   18 |  int res;
      |      ^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1016 ms 23008 KB Output is correct
5 Correct 741 ms 23032 KB Output is correct
6 Correct 1074 ms 19704 KB Output is correct
7 Correct 1041 ms 19696 KB Output is correct
8 Correct 669 ms 13176 KB Output is correct
9 Correct 977 ms 19696 KB Output is correct
10 Correct 945 ms 19320 KB Output is correct
11 Correct 1 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1422 ms 11316 KB Output is correct
13 Correct 1884 ms 5496 KB Output is correct
14 Correct 574 ms 2300 KB Output is correct
15 Correct 2250 ms 7204 KB Output is correct
16 Correct 585 ms 10796 KB Output is correct
17 Correct 1301 ms 8696 KB Output is correct
18 Correct 2047 ms 11348 KB Output is correct
19 Correct 1827 ms 11384 KB Output is correct
20 Correct 1778 ms 10936 KB Output is correct
21 Correct 1 ms 384 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1000 ms 22616 KB Output is correct
13 Correct 745 ms 22904 KB Output is correct
14 Correct 934 ms 19832 KB Output is correct
15 Correct 1061 ms 19616 KB Output is correct
16 Correct 645 ms 13320 KB Output is correct
17 Correct 1000 ms 19704 KB Output is correct
18 Correct 1087 ms 19308 KB Output is correct
19 Correct 1473 ms 12040 KB Output is correct
20 Correct 1894 ms 5548 KB Output is correct
21 Correct 582 ms 2572 KB Output is correct
22 Correct 2323 ms 7444 KB Output is correct
23 Correct 581 ms 11228 KB Output is correct
24 Correct 1317 ms 8800 KB Output is correct
25 Correct 2040 ms 11316 KB Output is correct
26 Correct 1881 ms 11396 KB Output is correct
27 Correct 1771 ms 10632 KB Output is correct
28 Correct 866 ms 100472 KB Output is correct
29 Correct 2289 ms 112888 KB Output is correct
30 Correct 4785 ms 80632 KB Output is correct
31 Correct 4487 ms 62480 KB Output is correct
32 Correct 593 ms 4480 KB Output is correct
33 Correct 801 ms 5624 KB Output is correct
34 Correct 1116 ms 109944 KB Output is correct
35 Correct 1638 ms 58668 KB Output is correct
36 Correct 2953 ms 111396 KB Output is correct
37 Correct 2414 ms 110840 KB Output is correct
38 Correct 2400 ms 110196 KB Output is correct
39 Correct 2068 ms 85880 KB Output is correct
40 Correct 1 ms 384 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1016 ms 23320 KB Output is correct
13 Correct 721 ms 23800 KB Output is correct
14 Correct 1012 ms 20984 KB Output is correct
15 Correct 1090 ms 20892 KB Output is correct
16 Correct 691 ms 14328 KB Output is correct
17 Correct 1033 ms 20856 KB Output is correct
18 Correct 974 ms 20364 KB Output is correct
19 Correct 1397 ms 12408 KB Output is correct
20 Correct 1903 ms 5660 KB Output is correct
21 Correct 572 ms 2652 KB Output is correct
22 Correct 2247 ms 7428 KB Output is correct
23 Correct 596 ms 11000 KB Output is correct
24 Correct 1254 ms 9020 KB Output is correct
25 Correct 2053 ms 11536 KB Output is correct
26 Correct 1855 ms 11668 KB Output is correct
27 Correct 1786 ms 11000 KB Output is correct
28 Correct 854 ms 100856 KB Output is correct
29 Correct 2328 ms 112716 KB Output is correct
30 Correct 4808 ms 80920 KB Output is correct
31 Correct 4442 ms 62208 KB Output is correct
32 Correct 579 ms 3320 KB Output is correct
33 Correct 776 ms 3832 KB Output is correct
34 Correct 1068 ms 108860 KB Output is correct
35 Correct 1594 ms 57160 KB Output is correct
36 Correct 2903 ms 110052 KB Output is correct
37 Correct 2599 ms 110200 KB Output is correct
38 Correct 2415 ms 109632 KB Output is correct
39 Correct 1253 ms 209400 KB Output is correct
40 Correct 3655 ms 235736 KB Output is correct
41 Correct 6278 ms 165928 KB Output is correct
42 Correct 5797 ms 127228 KB Output is correct
43 Correct 1687 ms 233208 KB Output is correct
44 Correct 819 ms 4600 KB Output is correct
45 Correct 1983 ms 86648 KB Output is correct
46 Correct 3723 ms 234104 KB Output is correct
47 Correct 4003 ms 234232 KB Output is correct
48 Correct 3762 ms 233824 KB Output is correct
49 Correct 1 ms 384 KB Output is correct