oj.uz

Submission #332962

# Submission time Handle Problem Language Result Execution time Memory
332962 2020-12-04T04:51:29 Z gmyu Game (IOI13_game) C++14
80 / 100
 4858 ms 256004 KB 
/*
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>

#include "game.h"

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;
}

/*
Naively, inserting N elements into a sparse segment tree requires O(N log C) memory, giving a bound of O(N log^2C) on 2D segment tree memory.
This is usually too much for N=C=10^5 and 256 MB
Possible ways to get around this:
- Use arrays of fixed size rather than pointers.
- Reduce the memory usage of sparse segment tree to $O(N)$ while maintaining the same O(N\log C) insertion time
(see the solution for IOI Game below for details).
- Use BBSTs instead of sparse segment trees: https://cp-algorithms.com/data_structures/treap.html
*/

/// 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, val;
};
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, 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(gcd2(g1, g2), ny[v].val);
}
void updY(int vty, ll val, int v, int l = NYseg[0], int r = NYseg[1]){
    if(l == r) { ny[v].g = val; ny[v].val = val; return; } // leaf

    int mid = (l + r) / 2;
    if(vty == mid) {
        ny[v].val = val;
    } else if (vty < mid) {
        if(mid-1 >= l) {
            if(ny[v].lp == -1) { nn = newNY(); ny[v].lp = nn; };
            updY(vty, val, ny[v].lp, l, mid -1);
        }
    } else {
        if(mid+1 <= r) {
            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 : ( (mid-1 >= l) ? queY(qle, qri, ny[v].lp, l, mid-1) : 0LL );
    ll g2 = (ny[v].rp == -1) ? 0LL : ( (mid+1 <= r) ? queY(qle, qri, ny[v].rp, mid+1, r) : 0LL );
    ll g3 = (qle <= mid && mid <= qri) ? ny[v].val : 0LL;
    return gcd2(gcd2(g1, g2), g3);
}
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);
    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(nx[v].treeV == -1) { nn = newNY(); nx[v].treeV = nn; }

    if(l == r) { updY(vty, val, nx[v].treeV); return; } // leaf

    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) 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);
    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 492 KB Output is correct
10 Correct 1 ms 364 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 0 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 569 ms 11884 KB Output is correct
5 Correct 536 ms 12432 KB Output is correct
6 Correct 646 ms 9228 KB Output is correct
7 Correct 749 ms 8076 KB Output is correct
8 Correct 429 ms 6032 KB Output is correct
9 Correct 676 ms 8588 KB Output is correct
10 Correct 624 ms 8332 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 492 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1117 ms 11276 KB Output is correct
13 Correct 1708 ms 4816 KB Output is correct
14 Correct 316 ms 1644 KB Output is correct
15 Correct 2013 ms 7016 KB Output is correct
16 Correct 250 ms 13148 KB Output is correct
17 Correct 852 ms 7932 KB Output is correct
18 Correct 1506 ms 13660 KB Output is correct
19 Correct 1287 ms 14172 KB Output is correct
20 Correct 1246 ms 13916 KB Output is correct
21 Correct 1 ms 364 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 492 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 544 ms 11920 KB Output is correct
13 Correct 530 ms 12048 KB Output is correct
14 Correct 618 ms 9284 KB Output is correct
15 Correct 670 ms 8076 KB Output is correct
16 Correct 431 ms 5996 KB Output is correct
17 Correct 666 ms 8588 KB Output is correct
18 Correct 638 ms 8332 KB Output is correct
19 Correct 1103 ms 11104 KB Output is correct
20 Correct 1691 ms 4736 KB Output is correct
21 Correct 326 ms 1644 KB Output is correct
22 Correct 2009 ms 7016 KB Output is correct
23 Correct 242 ms 13148 KB Output is correct
24 Correct 845 ms 8040 KB Output is correct
25 Correct 1508 ms 13660 KB Output is correct
26 Correct 1298 ms 14172 KB Output is correct
27 Correct 1237 ms 13956 KB Output is correct
28 Correct 1092 ms 200980 KB Output is correct
29 Correct 2342 ms 204180 KB Output is correct
30 Correct 4858 ms 200232 KB Output is correct
31 Correct 4514 ms 202296 KB Output is correct
32 Correct 619 ms 4464 KB Output is correct
33 Correct 802 ms 4964 KB Output is correct
34 Correct 802 ms 200340 KB Output is correct
35 Correct 1618 ms 103084 KB Output is correct
36 Correct 3050 ms 202136 KB Output is correct
37 Correct 2570 ms 202572 KB Output is correct
38 Correct 2528 ms 202260 KB Output is correct
39 Correct 2137 ms 202772 KB Output is correct
40 Correct 1 ms 364 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 492 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 544 ms 12048 KB Output is correct
13 Correct 534 ms 12176 KB Output is correct
14 Correct 609 ms 9156 KB Output is correct
15 Correct 682 ms 8076 KB Output is correct
16 Correct 432 ms 6032 KB Output is correct
17 Correct 659 ms 8588 KB Output is correct
18 Correct 621 ms 8332 KB Output is correct
19 Correct 1112 ms 11104 KB Output is correct
20 Correct 1731 ms 4792 KB Output is correct
21 Correct 306 ms 1644 KB Output is correct
22 Correct 2009 ms 7016 KB Output is correct
23 Correct 243 ms 13148 KB Output is correct
24 Correct 866 ms 8048 KB Output is correct
25 Correct 1466 ms 13788 KB Output is correct
26 Correct 1301 ms 14200 KB Output is correct
27 Correct 1242 ms 13788 KB Output is correct
28 Correct 1078 ms 201108 KB Output is correct
29 Correct 2362 ms 204196 KB Output is correct
30 Correct 4836 ms 200216 KB Output is correct
31 Correct 4496 ms 202496 KB Output is correct
32 Correct 615 ms 3312 KB Output is correct
33 Correct 799 ms 4836 KB Output is correct
34 Correct 787 ms 200340 KB Output is correct
35 Correct 1596 ms 102948 KB Output is correct
36 Correct 3020 ms 202220 KB Output is correct
37 Correct 2559 ms 202772 KB Output is correct
38 Correct 2529 ms 202260 KB Output is correct
39 Runtime error 871 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -