oj.uz

Submission #250317

# Submission time Handle Problem Language Result Execution time Memory
250317 2020-07-17T11:44:32 Z MarcoMeijer Game (IOI13_game) C++14
0 / 100
 1 ms 512 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
#define sz size()

int R, C;

ll gcd(ll X, ll Y) {
    ll tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct Seg {
    int bg, ed;
    ll val;
    Seg* ls=nullptr;
    Seg* rs=nullptr;

    Seg(int l, int r, ll v=0) {
        bg=l; ed=r; val=v;
    }
    ll f(Seg* s) {
        if(s == nullptr) return 0;
        return s->val;
    }
    ll f(Seg* s, int i, int j, int l, int r) {
        if(s == nullptr) return 0;
        return s->get(i,j,l,r);
    }
    void set(int i, ll v, int l, int r) {
        int m=(l+r)/2;
        if(l == r) {
            val = v;
            return;
        }
        if(i <= m) {
            if(ls == nullptr) ls = new Seg(l,m);
            ls->set(i,v,l,m);
        } else {
            if(rs == nullptr) rs = new Seg(m+1,r);
            rs->set(i,v,m+1,r);
        }
        val = gcd(f(ls), f(rs));
    }
    ll get(int i, int j, int l, int r) {
        if(j < l || i > r) return 0;
        if(i <= l && j >= r) return val;
        int m=(l+r)/2;
        ll a = f(ls,i,j,l,m);
        ll b = f(rs,i,j,m+1,r);
        return gcd(a,b);
    }
};

struct Seg2 {
    int bg, ed;
    Seg val;
    Seg2* ls=nullptr;
    Seg2* rs=nullptr;
    
    Seg2(int l, int r) : val(0,C-1) {
        bg = l; ed = r;
    }
    void set(int i, int j, ll v, int l, int r) {
        int m=(l+r)/2;
        val.set(j,v,0,C-1);
        if(l == r) {
            return;
        }
        if(i <= m) {
            if(ls == nullptr) ls = new Seg2(l,m);
            ls->set(i,j,v,l,m);
        } else {
            if(rs == nullptr) rs = new Seg2(m+1,r);
            rs->set(i,j,v,m+1,r);
        }
    }
    ll f(Seg2* s, int i, int j, int I, int J, int l, int r) {
        if(s == nullptr) return 0;
        return s->get(i,j,I,J,l,r);
    }
    ll get(int i, int j, int I, int J, int l, int r) {
        if(j < l || i > r) return 0;
        if(i <= l && j >= r) return val.get(I,J,0,C-1);
        int m=(l+r)/2;
        ll a = f(ls,i,j,I,J,l,m);
        ll b = f(rs,i,j,I,J,m+1,r);
        return gcd(a,b);
    }
};

Seg2* SEG;

void init(int _R, int _C) {
    R = _R;
    C = _C;
    SEG = new Seg2(0,R-1);
}

void update(int P, int Q, ll K) {
    SEG->set(P,Q,K,0,R-1);
}

ll calculate(int P, int Q, int U, int V) {
    return SEG->get(P,U,Q,V,0,R-1);
}

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;
      ^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Incorrect 1 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 0 ms 256 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Incorrect 1 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Incorrect 1 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Incorrect 1 ms 512 KB Output isn't correct
3 Halted 0 ms 0 KB -