oj.uz

답안 #108630

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
108630 2019-04-30T12:19:34 Z tictaccat 게임 (IOI13_game) C++11
10 / 100
 13000 ms 65188 KB 
#include "game.h"

typedef long long ll;

#include <bits/stdc++.h>

using namespace std;

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 Node {
    Node *left, *right;
    ll g;
    Node(): g(0), left(NULL), right(NULL) {}
};

struct st1 {
    Node* root = new Node(); int sz = 1e9 + 100;
    void upd(Node* cur, int x, int y, int pos, ll val) {
        if (x > pos || y < pos) return;
        if (x == y) {
            cur->g = val;
            return;
        }
        if (cur->left == NULL) cur->left = new Node();
        if (cur->right == NULL) cur->right = new Node();
        int mid = (x+y)/2;
        upd(cur->left,x,mid,pos,val);
        upd(cur->right,mid+1,y,pos,val);
    }
    ll query(Node* cur, int x, int y, int l, int r) {
        if (x > r || y < l) return 0;
        if (x == y) return cur->g;
        if (cur->left == NULL) cur->left = new Node();
        if (cur->right == NULL) cur->right = new Node();
        int mid = (x+y)/2;
        return gcd2(query(cur->left,x,mid,l,r), query(cur->right,mid+1,y,l,r));
    }  
    void upd(int pos, ll val) {
        upd(root,0,sz-1,pos,val);
    }
    ll query(int l, int r){
        return query(root,0,sz-1,l,r);
    }
};


struct Node2 {
    Node2 *left,*right;
    st1 st;
    Node2(): left(NULL), right(NULL) {}
};

struct st2 {
    Node2* root = new Node2(); int sz = 1e9 + 100;
    void upd(Node2* cur, int x, int y, int pos2, int pos1, ll val) {
        if (x > pos2 || y < pos2) return;
        if (x == y) {
            cur->st.upd(pos1,val);
            return;
        }
        if (cur->left == NULL) cur->left = new Node2();
        if (cur->right == NULL) cur->right = new Node2();
        int mid = (x+y)/2;
        upd(cur->left,x,mid,pos2,pos1,val);
        upd(cur->right,mid+1,y,pos2,pos1,val);
    }
    ll query(Node2* cur, int x, int y, int l2, int r2, int l1, int r1) {
        if (x > r2 || y < l2) return 0;
        if (x == y) return cur->st.query(l1,r1);
        if (cur->left == NULL) cur->left = new Node2();
        if (cur->right == NULL) cur->right = new Node2();
        int mid = (x+y)/2;
        return gcd2(query(cur->left,x,mid,l2,r2,l1,r1), query(cur->right,mid+1,y,l2,r2,l1,r1));
    }  
    void upd(int pos2, int pos1, ll val) {
        upd(root,0,sz-1,pos2,pos1,val);
    }
    ll query(int l2, int r2, int l1, int r1){
        return query(root,0,sz-1,l2,r2,l1,r1);
    }
} tr;

void init(int R, int C) {
    /* ... */
}

void update(int P, int Q, long long K) {
    /* ... */
    tr.upd(P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
    /* ... */
    if (P > U) swap(P,U);
    if (Q > V) swap(V,Q);
    return tr.query(P,U,Q,V);
}

// int main() {

//     st2 test;

//     test.upd(0,2,20);
//     test.upd(0,1,15);

//     cout << test.query(0,0,0,2);
  
//     return 0;
// }

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;
      ^~~
game.cpp: In constructor 'Node::Node()':
game.cpp:21:8: warning: 'Node::g' will be initialized after [-Wreorder]
     ll g;
        ^
game.cpp:20:11: warning:   'Node* Node::left' [-Wreorder]
     Node *left, *right;
           ^~~~
game.cpp:22:5: warning:   when initialized here [-Wreorder]
     Node(): g(0), left(NULL), right(NULL) {}
     ^~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Execution timed out 13092 ms 63192 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 5 ms 1152 KB Output is correct
3 Correct 5 ms 1152 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 4 ms 1152 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 4 ms 896 KB Output is correct
10 Correct 4 ms 1024 KB Output is correct
11 Correct 6 ms 640 KB Output is correct
12 Execution timed out 13012 ms 65188 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 5 ms 1152 KB Output is correct
3 Correct 6 ms 1152 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 5 ms 1152 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 3 ms 768 KB Output is correct
10 Correct 4 ms 1152 KB Output is correct
11 Correct 5 ms 632 KB Output is correct
12 Execution timed out 13072 ms 63324 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 1152 KB Output is correct
3 Correct 7 ms 1152 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 7 ms 1152 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 640 KB Output is correct
9 Correct 5 ms 896 KB Output is correct
10 Correct 5 ms 1152 KB Output is correct
11 Correct 5 ms 736 KB Output is correct
12 Execution timed out 13070 ms 63200 KB Time limit exceeded
13 Halted 0 ms 0 KB -