oj.uz

Submission #384170

# Submission time Handle Problem Language Result Execution time Memory
384170 2021-03-31T15:59:04 Z alishahali1382 Game (IOI13_game) C++14
0 / 100
 2 ms 384 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<#x<<", "<<#y<<" = "<<x<<", "<<y<<"\n";}
#define debugp(p) {cerr<<#p" = {"<<p.first<<", "<<p.second<<"}\n";}
#define pb push_back
#define all(x) x.begin(), x.end()

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

const int SEGSZ=20000000, SEGSZ2=2000000;

struct Node{
    ll val=0;
    Node *L=NULL, *R=NULL;
};

ll ans;
void Set(Node *v, int tl, int tr, int pos, ll val){
    if (!v) exit(0);
    if (tr-tl==1){
        (v->val)=val;
        return ;
    }
    int mid=(tl+tr)>>1;
    Node **son=&(pos<mid?(v->L):(v->R));
    if (!son) *son=new Node;
    Set(*son, mid, tr, pos, val);
    (v->val)=gcd2(((v->L)?v->L->val:0), ((v->R)?v->R->val:0));
    return ;
}
void Get(Node *v, int tl, int tr, int l, int r, ll &ans){
    if (r<=tl || tr<=l || !v) return ;
    if (l<=tl && tr<=r){
        ans=gcd2(ans, v->val); // overall log(10^18) for single query of problem
        return ;
    }
    int mid=(tl+tr)>>1;
    Get(v->L, tl, mid, l, r, ans);
    Get(v->R, mid, tr, l, r, ans);
}

int n, m, root;
int L2[SEGSZ2], R2[SEGSZ2], ts2;
Node *seg2[SEGSZ2];
int Set2(int id, int tl, int tr, int x, int y, ll val){
    if (!id) id=++ts2;
    if (!seg2[id]) seg2[id]=new Node;
    if (tr-tl==1) {
        Set(seg2[id], 0, m, y, val);
        return id;
    }
    int mid=(tl+tr)>>1;
    if (x<mid) L2[id]=Set2(L2[id], tl, mid, x, y, val);
    else R2[id]=Set2(R2[id], mid, tr, x, y, val);
    ll res=0;
    Get(seg2[L2[id]], 0, m, y, y+1, res);
    Get(seg2[R2[id]], 0, m, y, y+1, res);
    Set(seg2[id], 0, m, y, res);
    return id;
}
void Get2(int id, int tl, int tr, int l1, int l2, int r1, int r2){
    if (r1<=tl || tr<=l1 || !id) return ;
    if (l1<=tl && tr<=r1){
        // debug2(tl, tr)
        Get(seg2[id], 0, m, l2, r2, ans);
        return ;
    }
    int mid=(tl+tr)>>1;
    Get2(L2[id], tl, mid, l1, l2, r1, r2);
    Get2(R2[id], mid, tr, l1, l2, r1, r2);
}

void init(int nn, int mm) {
    n=nn;
    m=mm;
}

void update(int P, int Q, ll K){
    // debug("update")
    root=Set2(root, 0, n, P, Q, K);
    // debug("done")
}

ll calculate(int P, int Q, int U, int V) {
    ans=0;
    Get2(root, 0, n, P, Q, U+1, V+1);
    return ans;
}
/*
3 3 4
2 0 1 2 2
1 1 0 13
1 2 2 1
2 0 0 2 2

*/

Subtask #1
0 / 10.0

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

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 364 KB Output is correct
2 Incorrect 1 ms 364 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 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 20.0

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