Submission #838229

#	Time	Username	Problem	Language	Result	Execution time	Memory
838229		lohacho	Game (IOI13_game)	C++14	0 / 100	1 ms	340 KiB

game

#include "game.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;

int R, C;

struct Node1{
    long long val;
    int l, r, pos;
    Node1(){
        l = r = pos = -1;
        val = 0;
    }
};

struct Node2{
    int l, r, oid;
    Node2(){
        l = r = oid = -1;
    }
};

vector<Node1> tr1;
vector<Node2> tr2;

int newNode1(){
    int t = (int)tr1.size();
    tr1.push_back(Node1());
    return t;
}

int newNode2(){
    int t = (int)tr2.size();
    tr2.push_back(Node2());
    return t;
}

void push1(int x, int s, int e, int py, long long val){
    if(s == e){
        tr1[x].val = val;
        return;
    }

    int m = s + e >> 1;
    if(tr1[x].pos != -1){
        if(tr1[x].pos <= m){
            tr1[x].l = newNode1();
            tr1[tr1[x].l].val = tr1[x].val;
            tr1[tr1[x].l].pos = tr1[x].pos;
        }
        else{
            tr1[x].r = newNode1();
            tr1[tr1[x].r].val = tr1[x].val;
            tr1[tr1[x].r].pos = tr1[x].pos;
        }
        tr1[x].pos = -1;
    }

    // cout << "P1 " << x << ' ' << s << ' ' << e << ' ' << py << ' ' << val << endl;

    if(py <= m){
        if(tr1[x].l == -1){
            tr1[x].l = newNode1();
            tr1[tr1[x].l].val = val;
            tr1[tr1[x].l].pos = py;
        }
        else{
            push1(tr1[x].l, s, m, py, val);
        }
    }
    else{
        if(tr1[x].r == -1){
            tr1[x].r = newNode1();
            tr1[tr1[x].r].val = val;
            tr1[tr1[x].r].pos = py;
        }
        else{
            push1(tr1[x].r, m + 1, e, py, val);
        }
    }

    long long v = 0;
    if(tr1[x].l != -1) v = tr1[tr1[x].l].val;
    if(tr1[x].r != -1) v = __gcd(v, tr1[tr1[x].r].val);
    // cout << "P1 " << v << endl;
    tr1[x].val = v;
}

long long query1(int x, int s, int e, int fs, int fe){
    if(fe < s || fs > e) return 0;
    if(fs <= s && fe >= e) return tr1[x].val;
    if(tr1[x].pos != -1){
        if(fs <= tr1[x].pos && tr1[x].pos <= fe) return tr1[x].val;
        return 0;
    }

    int m = s + e >> 1;
    long long rv = 0;
    if(tr1[x].l != -1) rv = query1(tr1[x].l, s, m, fs, fe);
    if(tr1[x].r != -1) rv = __gcd(rv, query1(tr1[x].r, m + 1, e, fs, fe));

    return rv;
}

void push2(int x, int s, int e, int px, int py, long long pval){
    if(tr2[x].oid == -1) tr2[x].oid = newNode1();
    if(s == e){
        push1(tr2[x].oid, 0, C - 1, py, pval);
        return;
    }

    int m = s + e >> 1;
    if(px <= m){
        if(tr2[x].l == -1) tr2[x].l = newNode2();
        push2(tr2[x].l, s, m, px, py, pval);
    }
    else{
        if(tr2[x].r == -1) tr2[x].r = newNode2();
        push2(tr2[x].r, m + 1, e, px, py, pval);
    }

    long long v = 0;
    if(tr2[x].l != -1) v = query1(tr2[tr2[x].l].oid, 0, C - 1, py, py);
    if(tr2[x].r != -1) v = __gcd(v, query1(tr2[tr2[x].r].oid, 0, C - 1, py, py));

    // cout << x << ' ' << s << ' ' << e << ' ' << v << endl;

    push1(tr2[x].oid, 0, C - 1, py, v);
}

long long query2(int x, int s, int e, int fxs, int fxe, int fys, int fye){
    if(fxe < s || fxs > e) return 0;
    if(fxs <= s && fxe >= e){
        return query1(tr2[x].oid, 0, C - 1, fys, fye);
    }

    int m = s + e >> 1;
    long long rv = 0;
    if(tr2[x].l != -1) rv = query2(tr2[x].l, s, m, fxs, fxe, fys, fye);
    if(tr2[x].r != -1) rv = __gcd(rv, query2(tr2[x].r, m + 1, e, fxs, fxe, fys, fye));

    return rv;
}

void init(int R_, int C_) {
    R = R_;
    C = C_;
    newNode2();
    tr2[0].oid = newNode1();
}

void update(int P, int Q, long long K) {
    push2(0, 0, R - 1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return query2(0, 0, R - 1, P, U, Q, V);
}

Compilation message (stderr)

game.cpp: In function 'void push1(int, int, int, int, long long int)':
game.cpp:47:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   47 |     int m = s + e >> 1;
      |             ~~^~~
game.cpp: In function 'long long int query1(int, int, int, int, int)':
game.cpp:100:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |     int m = s + e >> 1;
      |             ~~^~~
game.cpp: In function 'void push2(int, int, int, int, int, long long int)':
game.cpp:115:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  115 |     int m = s + e >> 1;
      |             ~~^~~
game.cpp: In function 'long long int query2(int, int, int, int, int, int, int)':
game.cpp:140:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  140 |     int m = s + e >> 1;
      |             ~~^~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20