oj.uz

Submission #99193

# Submission time Handle Problem Language Result Execution time Memory
99193 2019-03-01T15:31:17 Z maruii Game (IOI13_game) C++14
0 / 100
 4 ms 384 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int R, C;
struct ST{
    struct Node{
        int l=0, r=0;
        ll v=0;
    };
    vector<Node> node;
    void update(int nn, int ns, int ne, int x, ll v){
        if(ns>x || ne<x) return;
        if(ns==ne){
            node[nn].v = v;
            return;
        }
        int m = ns+ne>>1;
        if(m<x){
            if(!node[nn].r) node[nn].r = node.size(), node.resize(node[nn].r+1);
            update(node[nn].r, m+1, ne, x, v);
        }
        else{
            if(!node[nn].l) node[nn].l = node.size(), node.resize(node[nn].l+1);
            update(node[nn].l, ns, m, x, v);
        }
        node[nn].v = __gcd(node[nn].l?node[node[nn].l].v:0ll, node[nn].r?node[node[nn].r].v:0ll);
    }
    ll query(int nn, int ns, int ne, int s, int e){
        if(ns>e || ne<s) return 0;
        if(s<=ns && ne<=e) return node[nn].v;
        int m = ns+ne>>1;
        return __gcd(node[nn].l?query(node[nn].l, ns, m, s, e):0ll, node[nn].r?query(node[nn].r, m+1, ne, s, e):0ll);
    }
};

struct ST2{
    struct Node{
        int l=0, r=0;
        ST v;
    };
    vector<Node> node;
    void update(int nn, int ns, int ne, int x, int xx, ll v){
        if(ns>x || ne<x) return;
        if(ns==ne){
            node[nn].v.update(0, 0, C, xx, v);
            return;
        }
        int m = ns+ne>>1;
        if(m<x){
            if(!node[nn].r) node[nn].r = node.size(), node.resize(node[nn].r+1), node[node[nn].r].v.node.resize(1);
            update(node[nn].r, m+1, ne, x, xx, v);
        }
        else{
            if(!node[nn].l) node[nn].l = node.size(), node.resize(node[nn].l+1), node[node[nn].l].v.node.resize(1);
            update(node[nn].l, ns, m, x, xx, v);
        }
        node[nn].v.update(0, 0, C, xx, v);
    }
    ll query(int nn, int ns, int ne, int s, int e, int ss, int ee){
        if(ns>e || ne<s) return 0;
        if(s<=ns && ne<=e) return node[nn].v.query(0, 0, C, ss, ee);
        int m = ns+ne>>1;
        return __gcd(node[nn].l?query(node[nn].l, ns, m, s, e, ss, ee):0ll, node[nn].r?query(node[nn].r, m+1, ne, s, e, ss, ee):0ll);
    }
} seg;

void init(int R_, int C_) {
    R = R_ - 1, C = C_ - 1;
    seg.node.resize(1);
    seg.node[0].v.node.resize(1);
}

void update(int P, int Q, ll K) {
    seg.update(0, 0, R, P, Q, K);
}

ll calculate(int P, int Q, int U, int V) {
    return seg.query(0, 0, R, P, U, Q, V);
}

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 member function 'void ST::update(int, int, int, int, ll)':
game.cpp:18:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = ns+ne>>1;
                 ~~^~~
game.cpp: In member function 'll ST::query(int, int, int, int, int)':
game.cpp:32:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = ns+ne>>1;
                 ~~^~~
game.cpp: In member function 'void ST2::update(int, int, int, int, int, ll)':
game.cpp:49:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = ns+ne>>1;
                 ~~^~~
game.cpp: In member function 'll ST2::query(int, int, int, int, int, int, int)':
game.cpp:63:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int m = ns+ne>>1;
                 ~~^~~

Subtask #1
0 / 10.0

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

Subtask #3
0 / 26.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 20.0

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