oj.uz

Submission #332908

# Submission time Handle Problem Language Result Execution time Memory
332908 2020-12-04T01:20:45 Z gmyu Game (IOI13_game) C++11
63 / 100
 2044 ms 256004 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 610 ms 18260 KB Output is correct
5 Correct 620 ms 18132 KB Output is correct
6 Correct 637 ms 15572 KB Output is correct
7 Correct 721 ms 11464 KB Output is correct
8 Correct 448 ms 10204 KB Output is correct
9 Correct 719 ms 12124 KB Output is correct
10 Correct 661 ms 11080 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 3 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 978 ms 14600 KB Output is correct
13 Correct 1563 ms 7988 KB Output is correct
14 Correct 315 ms 5740 KB Output is correct
15 Correct 1812 ms 9556 KB Output is correct
16 Correct 260 ms 17352 KB Output is correct
17 Correct 793 ms 14168 KB Output is correct
18 Correct 1424 ms 19656 KB Output is correct
19 Correct 1264 ms 23152 KB Output is correct
20 Correct 1136 ms 22728 KB Output is correct
21 Correct 1 ms 364 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 615 ms 18536 KB Output is correct
13 Correct 615 ms 18220 KB Output is correct
14 Correct 629 ms 15444 KB Output is correct
15 Correct 738 ms 11464 KB Output is correct
16 Correct 454 ms 10204 KB Output is correct
17 Correct 709 ms 12140 KB Output is correct
18 Correct 664 ms 11080 KB Output is correct
19 Correct 949 ms 14280 KB Output is correct
20 Correct 1535 ms 7892 KB Output is correct
21 Correct 306 ms 5740 KB Output is correct
22 Correct 1818 ms 9428 KB Output is correct
23 Correct 248 ms 17352 KB Output is correct
24 Correct 825 ms 13908 KB Output is correct
25 Correct 1401 ms 19528 KB Output is correct
26 Correct 1179 ms 23112 KB Output is correct
27 Correct 1127 ms 22856 KB Output is correct
28 Correct 951 ms 140620 KB Output is correct
29 Runtime error 2044 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 597 ms 18296 KB Output is correct
13 Correct 611 ms 18268 KB Output is correct
14 Correct 618 ms 15776 KB Output is correct
15 Correct 724 ms 11336 KB Output is correct
16 Correct 457 ms 10204 KB Output is correct
17 Correct 683 ms 12164 KB Output is correct
18 Correct 682 ms 11208 KB Output is correct
19 Correct 961 ms 14528 KB Output is correct
20 Correct 1556 ms 7764 KB Output is correct
21 Correct 308 ms 5740 KB Output is correct
22 Correct 1822 ms 9568 KB Output is correct
23 Correct 250 ms 17480 KB Output is correct
24 Correct 775 ms 13908 KB Output is correct
25 Correct 1378 ms 19528 KB Output is correct
26 Correct 1191 ms 22984 KB Output is correct
27 Correct 1135 ms 22880 KB Output is correct
28 Correct 976 ms 140492 KB Output is correct
29 Runtime error 2012 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -