Submission #332908

#	Time	Username	Problem	Language	Result	Execution time	Memory
332908		gmyu	Game (IOI13_game)	C++11	63 / 100	2044 ms	256004 KiB

game

#include "game.h"

/*
ID: USACO_template
LANG: C++
PROG: USACO
*/
#include <iostream>  //cin , cout
#include <fstream>   //fin, fout
#include <stdio.h>   // scanf , pringf
#include <cstdio>
#include <algorithm> // sort , stuff
#include <stack>     // stacks
#include <queue>     // queues
#include <map>
#include <string>

using namespace std;

typedef pair<int, int>          pii;
typedef vector<int>             vi;     /// adjlist without weight
typedef vector<pii>             vii;    /// adjlist with weight
typedef vector<pair<int,pii>>   vpip;   /// edge with weight
typedef long long               ll;

#define mp  make_pair
#define fst first
#define snd second
#define pb  push_back
#define trav(u, adj_v) for (auto& u: adj_v)

const int MOD = 1e9+7;  // 998244353;
const int MX  = 2e5+5;   //
const ll  INF = 1e18;    //

#define MAXV 100007
#define MAXE 100007

const int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1}; /// 4 directions
struct NODE {
    int x, y;
    int val;
    int visited;
    bool operator< (NODE b) const { return (x == b.x) ? (y < b.y) : (x < b.x); }
};
struct EDGE {
    int from, to;
    ll weight;
    bool operator<(EDGE other) const { return weight < other.weight; }
};

/// code from USACO examples
void setIO(string name) {
    ios_base::sync_with_stdio(0); cin.tie(0);
    freopen((name+".in").c_str(),"r",stdin);
    freopen((name+".out").c_str(),"w",stdout);
}
bool debug = false, submit = true;


long long gcd2(long long X, long long Y) {
    if(X == 0) return Y;
    if(Y == 0) return X;
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X; X = Y;
        Y = tmp % Y;
    }
    return X;
}


/// 2D segment tree
struct NODEX {
    int lp, rp;     // left ptr, right ptr
    int treeV;
};
vector<NODEX> nx;
int NXseg[2];

struct NODEY {
    int lp, rp;     // left ptr, right ptr
    ll g;
};
vector<NODEY> ny;
int NYseg[2];

int newNX(){ nx.pb((NODEX) {-1, -1, -1}); return nx.size() - 1; }
int newNY(){ ny.pb((NODEY) {-1, -1,  0}); return ny.size() - 1; }
int nn;

void pullY(int v) {
    ll g1 = (ny[v].lp == -1) ? 0 : ny[ny[v].lp].g;
    ll g2 = (ny[v].rp == -1) ? 0 : ny[ny[v].rp].g;
    ny[v].g = gcd2(g1, g2);
    if(debug) cout << "  .. pull Y " << ny[v].g << endl;
}
void updY(int vty, ll val, int v, int l = NYseg[0], int r = NYseg[1]){
    if(debug) cout << "  .. go to Y (" << l << "," << r << ")" << endl;
    if(l == r) { // leaf
        ny[v].g = val;
        if(debug) cout << " .. assign Y " << ny[v].g << endl;
        return;
    }

    int mid = (l + r) / 2;
    if (vty <= mid) {
        if(ny[v].lp == -1) { nn = newNY(); ny[v].lp = nn; };
        updY(vty, val, ny[v].lp, l, mid);
    } else {
        if(ny[v].rp == -1) { nn = newNY(); ny[v].rp = nn; };
        updY(vty, val, ny[v].rp, mid+1, r);
    }

    pullY(v);
}
ll queY(int qle, int qri, int v, int l = NYseg[0], int r = NYseg[1]) {
    if(r < qle || l > qri) return 0LL;
    if(qle <= l && r <= qri) return ny[v].g;

    int mid = (l + r) / 2;
    ll g1 = (ny[v].lp == -1) ? 0LL : queY(qle, qri, ny[v].lp, l, mid);
    ll g2 = (ny[v].rp == -1) ? 0LL : queY(qle, qri, ny[v].rp, mid+1, r);
    return gcd2(g1, g2);
}
void pullX(int vty, int v) {
    ll g1 = (nx[v].lp == -1) ? 0LL : queY(vty, vty, nx[nx[v].lp].treeV);
    ll g2 = (nx[v].rp == -1) ? 0LL : queY(vty, vty, nx[nx[v].rp].treeV);
    ll g0 = gcd2(g1, g2);
    if(debug) cout << "  pull up X, update Y seg at X=" << v << " of val=" << g1 << " " << g2 << " " << g0 << " for Y tree " << nx[v].treeV <<endl;
    updY(vty, g0, nx[v].treeV);
}
void updX(int vtx, int vty, ll val, int v = 0, int l = NXseg[0], int r = NXseg[1]){
    if(debug) cout << " come to X=" << v << " at (" << l << "," << r << ") with Y tree " << nx[v].treeV << endl;
    if(nx[v].treeV == -1) { nn = newNY(); nx[v].treeV = nn; }
    if(debug) cout << " come to X=" << v << " at (" << l << "," << r << ") with Y tree " << nx[v].treeV << endl;

    if(l == r) { // leaf
        if(debug) cout << "  at X leaf, update Y seg at X=" << v << " at (" << l << "," << r << ")" << " for Y tree " << nx[v].treeV << endl;
        updY(vty, val, nx[v].treeV);
        return;
    }

    int mid = (l + r) / 2;
    if (vtx <= mid) {
        if(nx[v].lp == -1) { nn = newNX(); nx[v].lp = nn; }
        updX(vtx, vty, val, nx[v].lp, l, mid);
    } else {
        if(nx[v].rp == -1) { nn = newNX(); nx[v].rp = nn; }
        updX(vtx, vty, val, nx[v].rp, mid+1, r);
    }

    pullX(vty, v);
}
ll queX(int qxle, int qxri, int qyle, int qyri, int v = 0, int l = NXseg[0], int r = NXseg[1]) {
    if(r < qxle || l > qxri) return 0LL;
    if(qxle <= l && r <= qxri) {
        if(debug) cout << "  at X leaf, que Y seg at X=" << v << " at (" << l << "," << r << ")" << endl;
        return (nx[v].treeV == -1) ? 0 : queY(qyle, qyri, nx[v].treeV);
    }

    int mid = (l + r) / 2;
    ll g1 = (nx[v].lp == -1) ? 0LL : queX(qxle, qxri, qyle, qyri, nx[v].lp, l, mid);
    ll g2 = (nx[v].rp == -1) ? 0LL : queX(qxle, qxri, qyle, qyri, nx[v].rp, mid+1, r);
    if(debug) cout << " que X=(" << l << "," << r << ") = " << gcd2(g1, g2) << endl;
    return gcd2(g1, g2);
}


void init(int R, int C) {
    NXseg[0] = 0; NXseg[1] = C - 1;
    NYseg[0] = 0; NYseg[1] = R - 1;
    newNX();
}

void update(int P, int Q, long long K) {
    updX(Q, P, K);
}

long long calculate(int y10, int x10, int y20, int x20) {
    int x1 = min(x10, x20), x2 = max(x10, x20);
    int y1 = min(y10, y20), y2 = max(y10, y20);
    return queX(x1, x2, y1, y2);
}

Compilation message (stderr)

game.cpp: In function 'void setIO(std::string)':
game.cpp:55:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   55 |     freopen((name+".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
game.cpp:56:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   56 |     freopen((name+".out").c_str(),"w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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