oj.uz

답안 #384167

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
384167 2021-03-31T15:48:05 Z alishahali1382 게임 (IOI13_game) C++14
63 / 100
 1974 ms 256004 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;
Node* Set(Node *v, int tl, int tr, int pos, ll val){
    // debug2(tl, tr)
    // debug(v)
    if (!v){
        // debug("shit")
        // new Node;
        v=new Node;
    }
    // debug("built new node")
    if (tr-tl==1){
        // debug("shit")
        (v->val)=val;
        // debug("did shit")
        return v;
    }
    // debug("going down")
    int mid=(tl+tr)>>1;
    if (pos<mid) (v->L)=Set((v->L), tl, mid, pos, val);
    else (v->R)=Set((v->R), mid, tr, pos, val);
    // debug("update?")
    (v->val)=gcd2(((v->L)?v->L->val:0), ((v->R)?v->R->val:0));
    // debug("updated")
    return v;
}
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;
    // cerr<<"update "<<val<<" in "<<tl<<" "<<tr<<"\n";
    if (tr-tl==1) {
        // debug("Set")
        seg2[id]=Set(seg2[id], 0, m, y, val);
        // debug("Seted")
        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);
    // debug2(L2[id], R2[id])
    // debug2(seg[seg2[L2[id]]], seg[seg2[R2[id]]])
    ll res=0;
    Get(seg2[L2[id]], 0, m, y, y+1, res);
    Get(seg2[R2[id]], 0, m, y, y+1, res);
    // debug(res)
    seg2[id]=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
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct

Subtask #2
27.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 570 ms 12780 KB Output is correct
5 Correct 416 ms 13084 KB Output is correct
6 Correct 432 ms 9952 KB Output is correct
7 Correct 487 ms 9836 KB Output is correct
8 Correct 328 ms 6892 KB Output is correct
9 Correct 486 ms 9992 KB Output is correct
10 Correct 450 ms 9452 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #3
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 942 ms 16108 KB Output is correct
13 Correct 1372 ms 6380 KB Output is correct
14 Correct 287 ms 1004 KB Output is correct
15 Correct 1631 ms 8940 KB Output is correct
16 Correct 251 ms 18412 KB Output is correct
17 Correct 734 ms 11500 KB Output is correct
18 Correct 1330 ms 18924 KB Output is correct
19 Correct 1124 ms 18964 KB Output is correct
20 Correct 1064 ms 18156 KB Output is correct
21 Correct 1 ms 512 KB Output is correct

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 492 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 576 ms 12780 KB Output is correct
13 Correct 413 ms 13036 KB Output is correct
14 Correct 432 ms 10096 KB Output is correct
15 Correct 482 ms 9708 KB Output is correct
16 Correct 333 ms 6764 KB Output is correct
17 Correct 490 ms 9836 KB Output is correct
18 Correct 452 ms 9560 KB Output is correct
19 Correct 946 ms 16108 KB Output is correct
20 Correct 1370 ms 6324 KB Output is correct
21 Correct 286 ms 1004 KB Output is correct
22 Correct 1637 ms 8700 KB Output is correct
23 Correct 248 ms 18328 KB Output is correct
24 Correct 745 ms 11500 KB Output is correct
25 Correct 1332 ms 18540 KB Output is correct
26 Correct 1152 ms 18796 KB Output is correct
27 Correct 1073 ms 18156 KB Output is correct
28 Correct 1062 ms 248928 KB Output is correct
29 Runtime error 1932 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 2 ms 492 KB Output is correct
3 Correct 2 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 567 ms 12760 KB Output is correct
13 Correct 415 ms 13292 KB Output is correct
14 Correct 441 ms 9836 KB Output is correct
15 Correct 494 ms 9708 KB Output is correct
16 Correct 322 ms 6764 KB Output is correct
17 Correct 471 ms 9836 KB Output is correct
18 Correct 445 ms 9580 KB Output is correct
19 Correct 950 ms 15980 KB Output is correct
20 Correct 1381 ms 6320 KB Output is correct
21 Correct 287 ms 1004 KB Output is correct
22 Correct 1616 ms 8960 KB Output is correct
23 Correct 250 ms 18284 KB Output is correct
24 Correct 750 ms 11544 KB Output is correct
25 Correct 1278 ms 18756 KB Output is correct
26 Correct 1117 ms 18924 KB Output is correct
27 Correct 1056 ms 18668 KB Output is correct
28 Correct 1065 ms 249084 KB Output is correct
29 Runtime error 1974 ms 256004 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -