oj.uz

Submission #410510

# Submission time Handle Problem Language Result Execution time Memory
410510 2021-05-22T20:51:44 Z ekrem Game (IOI13_game) C++
0 / 100
 1 ms 332 KB 
#include <bits/stdc++.h>
#include "game.h"
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define orta ((bas+son)/2)
#define oorta ((bbas+sson)/2)
#define mod 1000000007
#define MAXN 20000005
using namespace std;
// #define fail(s, x...) do { \
//      fprintf(stderr, s "\n", ## x); \
//      exit(1); \
//  } while(0)
 
 
typedef long long ll;
 
int n, m, son1, son2, sol[MAXN], sag[MAXN], seg[MAXN], sl[MAXN], sg[MAXN], bas[MAXN], son[MAXN];
ll val[MAXN];


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;
}

ll opr(ll X, ll Y) {
    return gcd2(X, Y);
}


int ver(int k){
    if(!k)return 0;
    if(!seg[k]){
        son2++;
        bas[son2] = 1;
        son[son2] = m;
        return seg[k] = son2;
    }
    else
        return seg[k];
}

int yeniver(int bs, int sn){
    ++son2;
    bas[son2]=bs;
    son[son2]=sn;
    return son2;
}
 
int slver(int k){
    return (!sl[k])?sl[k] = ++son2:sl[k];
}
 
int sgver(int k){
    return (!sg[k])?sg[k] = ++son2:sg[k];
}
 
int solver(int k){
    return (!sol[k])?sol[k] = ++son1:sol[k];
}
 
int sagver(int k){
    return (!sag[k])?sag[k] = ++son1:sag[k];
}
 
ll qu2(int k, int x, int y){
    if(!k or bas[k] > y or son[k] < x)
        return 0;
    if(bas[k] >= x and son[k] <= y)
        return val[k];
    return opr(qu2(sl[k], x, y), qu2(sg[k], x, y));
}
 
ll qu1(int k, int bas, int son, int x, int y, int xx, int yy){
    if(!k or bas > y or son < x)
        return 0;
    if(bas >= x and son <= y)
        return qu2(seg[k], xx, yy);
    return opr(qu1(sol[k], bas, orta, x, y, xx, yy), qu1(sag[k], orta + 1, son, x, y, xx, yy));
}
 
void up2(int k, int x, ll z){
    if(bas[k] == son[k]){
        val[k] = z;
        return;
    }
    int git = (x <= ((bas[k]+son[k])/2)) ? sl[k] : sg[k];
    if(!git){
        int of = ((x <= ((bas[k]+son[k])/2)) ? sl[k] : sg[k]) = yeniver(x, x);
        val[of] = z;
    }
    else if(bas[git] <= x and son[git] >= x)
            up2(git, x, z);
    else{
        int bbas = bas[k], sson = son[k];
        do{
            if(x <= oorta)
                sson = oorta;
            else
                bbas = oorta + 1;
        }while((x <= oorta) == (bas[git] <= oorta) );
        int of = ((x <= ((bas[k]+son[k])/2)) ? sl[k] : sg[k]) = yeniver(bbas, sson);
        (bas[git] <= oorta ? sl[of] : sg[of]) = git;
        up2(of, x, z);
    }
    val[k] = opr(val[sl[k]], val[sg[k]]);
}
 
void up1(int k, int bas, int son, int x, int y, ll z){
    if(bas == son){
        up2(ver(k), y, z);
        return;
    }
    if(x <= orta)
        up1(solver(k), bas, orta, x, y, z);
    else
        up1(sagver(k), orta + 1, son, x, y, z);
    z = opr(qu2(seg[sol[k]], y, y), qu2(seg[sag[k]], y, y));
    up2(ver(k), y, z);
}



void init(int R, int C) {
    n = R;
    m = C;
}

void update(int P, int Q, long long K) {
    up1(1, 1, n, P, Q, K);}

long long calculate(int P, int Q, int U, int V) {
    return qu1(1, 1, n, P, Q, U, V);
}

Compilation message

game.cpp:12:1: warning: multi-line comment [-Wcomment]
   12 | // #define fail(s, x...) do { \
      | ^

Subtask #1
0 / 10.0

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

Subtask #2
0 / 27.0

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

Subtask #3
0 / 26.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 20.0

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