oj.uz

Submission #290078

# Submission time Handle Problem Language Result Execution time Memory
290078 2020-09-03T11:36:50 Z Atill83 Game (IOI13_game) C++14
37 / 100
 1587 ms 256004 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = (int) 3e5 + 5;
typedef long long ll;
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 st{
    int l, r;
    vector<ll> t;
    
    void init(int ll, int rr, int C){
        l = ll;
        r = rr;
        t.resize(4*C, 0);
    }

    void upd(int v, int tl, int tr, int pos, ll val, vector<ll> &t1, vector<ll> &t2){
        if(l == r){
            if(tl == tr){
                t[v] = val;
            }else{
                int tm = (tl + tr) / 2;
                if(pos <= tm)
                    upd(2*v, tl, tm, pos, val, t1, t2);
                else upd(2*v + 1, tm + 1, tr, pos, val, t1, t2);
                t[v] = gcd2(t[2*v], t[2*v + 1]);
            }
        }else{
            if(tl == tr){
                t[v] = gcd2(t1[v], t2[v]);
            }else{
                int tm = (tl + tr) / 2;
                if(pos <= tm)
                    upd(2*v, tl, tm, pos, val, t1, t2);
                else upd(2*v + 1, tm + 1, tr, pos, val, t1, t2);
                t[v] = gcd2(t1[v], t2[v]);
            }
        }
    }
    ll que(int v, int tl, int tr, int l, int r){
        if(l > r) return -1;
        else if(tl == l && tr == r){
            return t[v];
        }else{
            int tm = (tl + tr) / 2;
            ll ans1 = que(2*v, tl, tm, l, min(tm ,r)), ans2 = que(2*v + 1, tm + 1, tr, max(tm + 1, l), r);
            if(ans1 == -1) return ans2;
            else if(ans2 == -1) return ans1;
            else return gcd2(ans1, ans2);
        }
    }
} t[4*MAXN];
int c, r;
void build(int v, int tl, int tr){
    if(tl == tr){
        t[v].init(tl, tr, c);
    }else{
        int tm = (tl + tr) / 2;
        build(2*v, tl, tm);
        build(2*v+1, tm + 1, tr);
        t[v].init(tl, tr, c);
    }
}


void upd(int v, int tl, int tr, int posX, int posY, ll val){
    if(tl == tr){
        t[v].upd(1, 0, c - 1, posY, val, t[v].t, t[v].t);
    }else{
        int tm = (tl + tr) / 2;
        if(posX <= tm) upd(2*v, tl, tm, posX, posY, val);
        else upd(2*v+1, tm + 1, tr, posX, posY, val);
        t[v].upd(1, 0, c - 1, posY, val, t[2*v].t, t[2*v + 1].t);
    }
}

ll que(int v, int tl, int tr, int l1, int r1, int l2, int r2){
    if(l1 > r1) return -1;
    else if(tl == l1 && tr == r1){
        return t[v].que(1, 0, c - 1, l2, r2);
    }else{
        int tm = (tl + tr) / 2;
        ll ans1 = que(2*v, tl, tm, l1, min(tm, r1), l2, r2), ans2 = que(2*v + 1, tm + 1, tr, max(tm + 1, l1), r1, l2, r2);
        if(ans1 == -1) return ans2;
        else if(ans2 == -1) return ans1;
        else return gcd2(ans1, ans2);
    }
}



void init(int R, int C) {
    c = C;
    r = R;
    build(1, 0, R - 1);
}

void update(int P, int Q, long long K) {
    upd(1, 0, r - 1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return que(1, 0, r - 1, 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]
   18 |  int res;
      |      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 38008 KB Output is correct
2 Correct 30 ms 38648 KB Output is correct
3 Correct 29 ms 38520 KB Output is correct
4 Correct 26 ms 37888 KB Output is correct
5 Correct 26 ms 38528 KB Output is correct
6 Correct 27 ms 38520 KB Output is correct
7 Correct 26 ms 37888 KB Output is correct
8 Correct 26 ms 38144 KB Output is correct
9 Correct 28 ms 38528 KB Output is correct
10 Correct 25 ms 38528 KB Output is correct
11 Correct 28 ms 38560 KB Output is correct
12 Correct 26 ms 38016 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 37888 KB Output is correct
2 Correct 26 ms 37864 KB Output is correct
3 Correct 26 ms 37888 KB Output is correct
4 Correct 1018 ms 104268 KB Output is correct
5 Correct 627 ms 104312 KB Output is correct
6 Correct 814 ms 101656 KB Output is correct
7 Correct 822 ms 101240 KB Output is correct
8 Correct 749 ms 101748 KB Output is correct
9 Correct 843 ms 101372 KB Output is correct
10 Correct 803 ms 100916 KB Output is correct
11 Correct 26 ms 37888 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 37940 KB Output is correct
2 Correct 27 ms 38528 KB Output is correct
3 Correct 28 ms 38520 KB Output is correct
4 Correct 26 ms 37888 KB Output is correct
5 Correct 26 ms 38528 KB Output is correct
6 Correct 28 ms 38528 KB Output is correct
7 Correct 26 ms 37880 KB Output is correct
8 Correct 29 ms 38136 KB Output is correct
9 Correct 28 ms 38528 KB Output is correct
10 Correct 28 ms 38528 KB Output is correct
11 Correct 29 ms 38648 KB Output is correct
12 Correct 1118 ms 107772 KB Output is correct
13 Correct 1555 ms 104720 KB Output is correct
14 Runtime error 145 ms 256004 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 37896 KB Output is correct
2 Correct 27 ms 38520 KB Output is correct
3 Correct 27 ms 38528 KB Output is correct
4 Correct 26 ms 37888 KB Output is correct
5 Correct 28 ms 38528 KB Output is correct
6 Correct 26 ms 38520 KB Output is correct
7 Correct 30 ms 38008 KB Output is correct
8 Correct 29 ms 38016 KB Output is correct
9 Correct 28 ms 38528 KB Output is correct
10 Correct 26 ms 38528 KB Output is correct
11 Correct 28 ms 38528 KB Output is correct
12 Correct 962 ms 104460 KB Output is correct
13 Correct 622 ms 104312 KB Output is correct
14 Correct 806 ms 101752 KB Output is correct
15 Correct 831 ms 101192 KB Output is correct
16 Correct 721 ms 101624 KB Output is correct
17 Correct 844 ms 101368 KB Output is correct
18 Correct 765 ms 100948 KB Output is correct
19 Correct 1097 ms 107896 KB Output is correct
20 Correct 1524 ms 104696 KB Output is correct
21 Runtime error 139 ms 256000 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 37888 KB Output is correct
2 Correct 24 ms 38580 KB Output is correct
3 Correct 27 ms 38528 KB Output is correct
4 Correct 25 ms 37948 KB Output is correct
5 Correct 27 ms 38528 KB Output is correct
6 Correct 26 ms 38560 KB Output is correct
7 Correct 25 ms 38016 KB Output is correct
8 Correct 27 ms 38144 KB Output is correct
9 Correct 26 ms 38528 KB Output is correct
10 Correct 26 ms 38520 KB Output is correct
11 Correct 26 ms 38528 KB Output is correct
12 Correct 965 ms 104444 KB Output is correct
13 Correct 635 ms 104440 KB Output is correct
14 Correct 817 ms 101568 KB Output is correct
15 Correct 798 ms 101316 KB Output is correct
16 Correct 694 ms 101892 KB Output is correct
17 Correct 820 ms 101368 KB Output is correct
18 Correct 794 ms 101112 KB Output is correct
19 Correct 1166 ms 107884 KB Output is correct
20 Correct 1587 ms 104392 KB Output is correct
21 Runtime error 153 ms 256004 KB Execution killed with signal 9
22 Halted 0 ms 0 KB -