oj.uz

Submission #66102

# Submission time Handle Problem Language Result Execution time Memory
66102 2018-08-09T14:45:28 Z FLDutchman Game (IOI13_game) C++14
0 / 100
 4 ms 544 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

#define mp make_pair
#define pb push_back
#define fst first
#define snd second
#define fast_io() ios::sync_with_stdio(false)
#define FOR(i, l, r) for(int i = (l); i < (r); i++)
#define H(x) cout << #x << " " << x << endl;

typedef long long ll;
typedef pair<ll, ll> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef set<int> si;
typedef double ld;
typedef pair<ld, ld> dd;

const ll INF = 1000000000000000000LL;
const int NMAX = 1e6+4;
const int mod = 1e9+7;
const ld eps = 1e-10;
const ld PI = acos(-1);


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 segtree {
    segtree *l, *r;
    long long gcd = 0;
    segtree* lc(){
        if(!l) l = new segtree();
        return l;
    }
    segtree* rc(){
        if(!r) r = new segtree();
        return r;
    }
};

int XMAX, YMAX;
segtree* t;

void upd( segtree *t, int x, int y, long long v, int xl, int xr, int yl, int yr ){
    if(xr - xl == 1 and yr - yl == 1) {
        t->gcd = v;
        return;
    }
    if(xr-xl == 1) {
        upd(t, y, x, v, yl, yr, xl, xr);
        t->gcd = gcd2(t->lc()->gcd, t->rc()->gcd);
        return;
    }
    auto l = t->lc(), r = t->rc();
    int xm = (xl + xr)/2;
    if(x < xm) upd(l, y, x, v, yl, yr, xl, xm);
    else upd(r, y, x, v, yl, yr, xm, xr);
    t->gcd = gcd2(l->gcd, r->gcd);
}

long long query(segtree *t, int qxl, int qxr, int qyl, int qyr, int xl, int xr, int yl, int yr){
    if(qxl <= xl and xr <= qxr and qyl <= yl and yr <= qyr) return t->gcd;
    if(xr-xl == 1) {
        return query(t, qyl, qyr, qxl, qxr, yl, yr, xl, xr);
    }
    int xm = (xl+xr)/2;
    long long gcd = 0;
    if(qxl < xm) {int tmp = query(t->lc(), qyl, qyr, qxl, qxr, yl, yr, xl, xm); gcd = gcd == 0 ? tmp : gcd2(gcd, tmp);}
    if(qxr > xm) {int tmp = query(t->rc(), qyl, qyr, qxl, qxr, yl, yr, xm, xr); gcd = gcd == 0 ? tmp : gcd2(gcd, tmp);}
    //cout << qxl << " " << qxr << " " << qyl << " " << qyr << " " << xl << " " << xr << " " << yl << " " << yr << " " << gcd << endl; 
    return gcd;
}

void init(int R, int C) {
    XMAX = 1e9;
    YMAX = 1e9;
    
    t = new segtree();
}

void update(int P, int Q, long long K) {
    upd(t, P, Q, K, 0, XMAX, 0, YMAX);
}

long long calculate(int P, int Q, int U, int V) {
    return query(t, min(P, U), max(P, U)+1, min(Q, V), max(Q, V)+1, 0, XMAX, 0, YMAX);
}

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 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

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

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 544 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 544 KB Output isn't correct
2 Halted 0 ms 0 KB -