oj.uz

Submission #290006

# Submission time Handle Problem Language Result Execution time Memory
290006 2020-09-03T09:48:38 Z egekabas Game (IOI13_game) C++14
37 / 100
 13000 ms 10152 KB 
    #include "game.h"
    #include <bits/stdc++.h>
    #define all(x) (x).begin(), (x).end()
    #define ff first
    #define ss second
    #define pb push_back
    #define mp make_pair
    using namespace std;
    typedef long long ll;
    typedef unsigned long long ull;
    typedef long double ld;
    typedef pair<ll, ll> pll;
    typedef pair<ull, ull> pull;
    typedef pair<ll, ll> pii;
    typedef pair<ld, ld> pld;
    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 node{
        ll tl, tr, val;
        node *l = nullptr, *r = nullptr;
        node(ll tlval, ll trval){
            tl = tlval;
            tr = trval;
            val = 0;
        }
        node(){}
        void upd(ll idx, ll nv){
            if(tl == idx && tr == idx){
                val = nv;
                return;
            }
            ll tm = (tl+tr)/2;
            if(idx <= tm){
                if(!l)
                    l = new node(tl, tm);
                l->upd(idx, nv);
            }
            else{
                if(!r)
                    r = new node(tm+1, tr);
                r->upd(idx, nv);
            }
            ll xval = 0, yval = 0;
            if(l)
                xval =  l->val;
            if(r)
                yval = r->val;
            val = gcd2(xval, yval);        
        }
        ll get(ll lef, ll rig){
            
            if(tr < lef || rig < tl)
                return 0;
            if(lef <= tl && tr <= rig){
                return val;
            }
            ll xval = 0, yval = 0;
            if(l)
                xval = l->get(lef, rig);
            if(r)
                yval = r->get(lef, rig);
            return gcd2(xval, yval);
        }
    };
    ll r, c;
    struct seg{
        ll tl, tr;
        node *val;
        seg *l = nullptr, *r = nullptr;
        seg(ll tval, ll rval){
            tl = tval;
            tr = rval;
            val = new node(0, c-1);
        }
        seg(){}
        void upd(ll xidx, ll yidx, ll nv){
            val->upd(yidx, nv);
            if(tl == xidx && tr == xidx){
                return;
            }
            ll tm = (tl+tr)/2;
            if(xidx <= tm){
                if(!l)
                    l = new seg(tl, tm);
                l->upd(xidx, yidx, nv);
            }
            else{
                if(!r)
                    r = new seg(tm+1, tr);
                r->upd(xidx, yidx, nv);
            }
        }
        ll get(ll xl, ll xr, ll yl, ll yr){
            if(tr < xl || xr < tl)
                return 0;
            if(xl <= tl && tr <= xr){
                return val->get(yl, yr);
            }
            ll xval = 0, yval = 0;
            if(l)
                xval = l->get(xl, xr, yl, yr);
            if(r)
                yval = r->get(xl, xr, yl, yr);
            return gcd2(xval, yval);
        }
    };
    seg root;
    node ar[2009];
    void init(int R, int C) {
        r = R;
        c = C;
        for(int i = 0; i < r; ++i)
            ar[i] = node(0, c-1);
        //root = seg(0, r-1);
    }
     
    void update(int P, int Q, long long K) {
        ar[P].upd(Q, K);
        //root.upd(P, Q, K);
    }
     
    long long calculate(int P, int Q, int U, int V){    
        ll ans = 0;
        for(int i = P; i <= U; ++i)
            ans = gcd2(ans, ar[i].get(Q, V));
        return ans;
        return root.get(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 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 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 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 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 752 ms 8056 KB Output is correct
5 Correct 451 ms 8444 KB Output is correct
6 Correct 648 ms 5240 KB Output is correct
7 Correct 736 ms 5112 KB Output is correct
8 Correct 468 ms 4216 KB Output is correct
9 Correct 684 ms 5368 KB Output is correct
10 Correct 648 ms 4984 KB Output is correct
11 Correct 1 ms 384 KB Output is correct

Subtask #3
0 / 26.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 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Execution timed out 13051 ms 9880 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.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 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 767 ms 8440 KB Output is correct
13 Correct 469 ms 8440 KB Output is correct
14 Correct 614 ms 5244 KB Output is correct
15 Correct 722 ms 5180 KB Output is correct
16 Correct 467 ms 4520 KB Output is correct
17 Correct 715 ms 5112 KB Output is correct
18 Correct 672 ms 4808 KB Output is correct
19 Execution timed out 13012 ms 10152 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.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 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 798 ms 8152 KB Output is correct
13 Correct 462 ms 8420 KB Output is correct
14 Correct 647 ms 5284 KB Output is correct
15 Correct 733 ms 5112 KB Output is correct
16 Correct 497 ms 4260 KB Output is correct
17 Correct 703 ms 5240 KB Output is correct
18 Correct 668 ms 4716 KB Output is correct
19 Execution timed out 13054 ms 9964 KB Time limit exceeded
20 Halted 0 ms 0 KB -