oj.uz

Submission #152460

# Submission time Handle Problem Language Result Execution time Memory
152460 2019-09-08T04:03:32 Z arnold518 Game (IOI13_game) C++14
0 / 100
 5 ms 632 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;

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

int R, C;

struct Node1
{
    ll val; int lc, rc;
    Node1() : val(0), lc(-1), rc(-1) {}
};
vector<Node1> nodes1;
int newNode1()
{
    nodes1.push_back(Node1());
    return nodes1.size()-1;
}

struct Node2
{
    int val; int lc, rc;
    Node2() : val(-1), lc(-1), rc(-1) {}
};
vector<Node2> nodes2;
int newNode2()
{
    nodes2.push_back(Node2());
    return nodes2.size()-1;
}

void update1(int node, int tl, int tr, int x, ll val)
{
    if(tl==tr)
    {
        nodes1[node].val=val;
        return;
    }
    int mid=tl+tr>>1;
    if(x<=mid)
    {
        if(nodes1[node].lc==-1) nodes1[node].lc=newNode1();
        update1(nodes1[node].lc, tl, mid, x, val);
    }
    else
    {
        if(nodes1[node].rc!=-1) nodes1[node].rc=newNode1();
        update1(nodes1[node].rc, mid+1, tr, x, val);
    }
    ll t=0;
    if(nodes1[node].lc!=-1) t=__gcd(t, nodes1[nodes1[node].lc].val);
    if(nodes1[node].rc!=-1) t=__gcd(t, nodes1[nodes1[node].rc].val);
    nodes1[node].val=t;
}

ll query1(int node, int tl, int tr, int xl, int xr)
{
    if(xr<tl || tr<xl) return 0;
    if(xl<=tl && tr<=xr) return nodes1[node].val;
    int mid=tl+tr>>1;
    ll ret=0;
    if(nodes1[node].lc!=-1) ret=__gcd(ret, query1(nodes1[node].lc, tl, mid, xl, xr));
    if(nodes1[node].rc!=-1) ret=__gcd(ret, query1(nodes1[node].rc, mid+1, tr, xl, xr));
    return ret;
}

void update2(int node, int tl, int tr, int y, int x, ll val)
{
    //printf("%d %d %d %d %d %lld\n", node, tl, tr, y, x, val);
    if(nodes2[node].val==-1) nodes2[node].val=newNode1();
    if(tl==tr)
    {
        update1(nodes2[node].val, 1, C, x, val);
        return;
    }
    int mid=tl+tr>>1;
    if(y<=mid)
    {
        if(nodes2[node].lc==-1) nodes2[node].lc=newNode2();
        update2(nodes2[node].lc, tl, mid, y, x, val);
    }
    else
    {
        if(nodes2[node].rc==-1) nodes2[node].rc=newNode2();
        update2(nodes2[node].rc, mid+1, tr, y, x, val);
    }
    ll t=0;
    if(nodes2[node].lc!=-1) t=__gcd(t, query1(nodes2[nodes2[node].lc].val, 1, C, x, x));
    if(nodes2[node].rc!=-1) t=__gcd(t, query1(nodes2[nodes2[node].rc].val, 1, C, x, x));
    update1(nodes2[node].val, 1, C, x, val);
}

ll query2(int node, int tl, int tr, int yl, int yr, int xl, int xr)
{
    if(yr<tl || tr<yl) return 0;
    if(yl<=tl && tr<=yr)
    {
        if(nodes2[node].val!=-1) return query1(nodes2[node].val, 1, C, xl, xr);
        else return 0;
    }
    int mid=tl+tr>>1;
    ll ret=0;
    if(nodes2[node].lc!=-1) ret=__gcd(ret, query2(nodes2[node].lc, tl, mid, yl, yr, xl, xr));
    if(nodes2[node].rc!=-1) ret=__gcd(ret, query2(nodes2[node].rc, mid+1, tr, yl, yr, xl, xr));
    return ret;
}

int root;

void init(int _R, int _C)
{
    int i, j;
    R=_R; C=_C;
    root=newNode2();
}

void update(int P, int Q, ll K)
{
    int i, j;
    P++; Q++;
    update2(root, 1, R, P, Q, K);
}

ll calculate(int P, int Q, int U, int V)
{
    int i, j;
    P++; Q++; U++; V++;
    return query2(root, 1, 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 function 'void update1(int, int, int, int, ll)':
game.cpp:42:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
game.cpp: In function 'll query1(int, int, int, int, int)':
game.cpp:63:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
game.cpp: In function 'void update2(int, int, int, int, int, ll)':
game.cpp:79:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
game.cpp: In function 'll query2(int, int, int, int, int, int, int)':
game.cpp:104:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=tl+tr>>1;
             ~~^~~
game.cpp: In function 'void init(int, int)':
game.cpp:115:9: warning: unused variable 'i' [-Wunused-variable]
     int i, j;
         ^
game.cpp:115:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
game.cpp: In function 'void update(int, int, ll)':
game.cpp:122:9: warning: unused variable 'i' [-Wunused-variable]
     int i, j;
         ^
game.cpp:122:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
game.cpp: In function 'll calculate(int, int, int, int)':
game.cpp:129:9: warning: unused variable 'i' [-Wunused-variable]
     int i, j;
         ^
game.cpp:129:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Runtime error 5 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Runtime error 2 ms 376 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Runtime error 5 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Runtime error 5 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Runtime error 5 ms 632 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -