Submission #332942

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
332942	2020-12-04T03:31:30 Z	gmyu	Game (IOI13_game)	C++14	100 / 100	7891 ms	57032 KB

game

/*
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

/// 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 with Treap on Y to reduce memory

struct NODEY {
    int key, priority;
    long long val, ans;
    NODEY *l, *r;

    NODEY(int _key, long long _val) : key(_key), priority(rand() + (rand() << 15)), val(_val), ans(_val), l(NULL), r(NULL) {}
};
typedef NODEY* pNODEY;
int NYseg[2];

long long ans(pNODEY t) { return t ? t->ans : 0; }
void pullY(pNODEY t) {
    if (t) t->ans = gcd2(gcd2(ans(t->l), ans(t->r)), t->val);
}
void splitY(pNODEY t, int key, pNODEY &l, pNODEY &r) {
    if (!t)
        l = r = NULL;
    else if (key < t->key)
        splitY(t->l, key, l, t->l), r = t;
    else
        splitY(t->r, key, t->r, r), l = t;
    pullY(t);
}
void mergeY(pNODEY &t, pNODEY l, pNODEY r) {
    if (!l || !r)
        t = l ? l : r;
    else if (l->priority > r->priority)
        mergeY(l->r, l->r, r), t = l;
    else
        mergeY(r->l, l, r->l), t = r;
    pullY(t);
}
long long queY(int l, int r, pNODEY t) {    // [l, r]
    pNODEY pl, pm, pr;
    splitY(t, l-1, pl, pm); splitY(pm, r, t, pr);
    long long ret = ans(t);
    mergeY(pm, pl, t); mergeY(t, pm, pr);
    return ret;
}
void updY(int p, long long val, pNODEY &t) {
    pNODEY pl, pm, pr;
    splitY(t, p-1, pl, pm); splitY(pm, p, t, pr);
    if (t) t->val = t->ans = val;
    else t = new NODEY(p, val);
    mergeY(pm, pl, t); mergeY(t, pm, pr);
}

struct NODEX {
    NODEX *lp, *rp;     // left ptr, right ptr
    pNODEY pny;
    NODEX() : lp(NULL), rp(NULL), pny(NULL) {}
};
NODEX nx;
int NXseg[2];

void pullX(int vty, NODEX *pnx) {
    ll g1 = (!pnx->lp) ? 0LL : queY(vty, vty, pnx->lp->pny);
    ll g2 = (!pnx->rp) ? 0LL : queY(vty, vty, pnx->rp->pny);
    ll g0 = gcd2(g1, g2);
    updY(vty, g0, pnx->pny);
}
void updX(int vtx, int vty, ll val, NODEX *pnx, int l = NXseg[0], int r = NXseg[1]){
    if(l == r) { updY(vty, val, pnx->pny); return; } // leaf

    int mid = (l + r) / 2;
    if (vtx <= mid) {
        if(!pnx->lp) pnx->lp = new NODEX();
        updX(vtx, vty, val, pnx->lp, l, mid);
    } else {
        if(!pnx->rp) pnx->rp = new NODEX();
        updX(vtx, vty, val, pnx->rp, mid+1, r);
    }

    pullX(vty, pnx);
}
ll queX(int qxle, int qxri, int qyle, int qyri, NODEX *pnx, int l = NXseg[0], int r = NXseg[1]) {    // [l, r]
    if(r < qxle || l > qxri) return 0LL;
    if(qxle <= l && r <= qxri) return queY(qyle, qyri, pnx->pny);

    int mid = (l + r) / 2;
    ll g1 = (!pnx->lp) ? 0LL : queX(qxle, qxri, qyle, qyri, pnx->lp, l, mid);
    ll g2 = (!pnx->rp) ? 0LL : queX(qxle, qxri, qyle, qyri, pnx->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;
}

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

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, &nx);
}

Compilation message

game.cpp: In function 'void setIO(std::string)':
game.cpp:42:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   42 |     freopen((name+".in").c_str(),"r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
game.cpp:43:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   43 |     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	2 ms	364 KB	Output is correct
3	Correct	2 ms	364 KB	Output is correct
4	Correct	0 ms	364 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	2 ms	364 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	0 ms	364 KB	Output is correct

Subtask #2

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 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	864 ms	9464 KB	Output is correct
5	Correct	1075 ms	9836 KB	Output is correct
6	Correct	1601 ms	6636 KB	Output is correct
7	Correct	1892 ms	6508 KB	Output is correct
8	Correct	949 ms	4972 KB	Output is correct
9	Correct	1790 ms	6508 KB	Output is correct
10	Correct	1586 ms	6124 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	2 ms	364 KB	Output is correct
3	Correct	2 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	2 ms	364 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	1793 ms	8172 KB	Output is correct
13	Correct	3720 ms	3596 KB	Output is correct
14	Correct	550 ms	876 KB	Output is correct
15	Correct	4046 ms	4004 KB	Output is correct
16	Correct	542 ms	5740 KB	Output is correct
17	Correct	2275 ms	4216 KB	Output is correct
18	Correct	4054 ms	6308 KB	Output is correct
19	Correct	3420 ms	6548 KB	Output is correct
20	Correct	3194 ms	5724 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	1 ms	364 KB	Output is correct
2	Correct	2 ms	364 KB	Output is correct
3	Correct	2 ms	364 KB	Output is correct
4	Correct	0 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 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	384 KB	Output is correct
12	Correct	868 ms	9376 KB	Output is correct
13	Correct	1077 ms	9836 KB	Output is correct
14	Correct	1657 ms	6596 KB	Output is correct
15	Correct	1881 ms	6252 KB	Output is correct
16	Correct	963 ms	4848 KB	Output is correct
17	Correct	1744 ms	6500 KB	Output is correct
18	Correct	1585 ms	6328 KB	Output is correct
19	Correct	1802 ms	8300 KB	Output is correct
20	Correct	3717 ms	3308 KB	Output is correct
21	Correct	547 ms	1132 KB	Output is correct
22	Correct	4016 ms	3944 KB	Output is correct
23	Correct	530 ms	5740 KB	Output is correct
24	Correct	2234 ms	4204 KB	Output is correct
25	Correct	4111 ms	6124 KB	Output is correct
26	Correct	3479 ms	6384 KB	Output is correct
27	Correct	3220 ms	5740 KB	Output is correct
28	Correct	1471 ms	21100 KB	Output is correct
29	Correct	2660 ms	34284 KB	Output is correct
30	Correct	5300 ms	23936 KB	Output is correct
31	Correct	4843 ms	20320 KB	Output is correct
32	Correct	741 ms	10252 KB	Output is correct
33	Correct	1106 ms	10476 KB	Output is correct
34	Correct	718 ms	27884 KB	Output is correct
35	Correct	2700 ms	21708 KB	Output is correct
36	Correct	5415 ms	32008 KB	Output is correct
37	Correct	4180 ms	32236 KB	Output is correct
38	Correct	4231 ms	31592 KB	Output is correct
39	Correct	3450 ms	27300 KB	Output is correct
40	Correct	1 ms	492 KB	Output is correct

Subtask #5

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	364 KB	Output is correct
2	Correct	2 ms	364 KB	Output is correct
3	Correct	2 ms	364 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	364 KB	Output is correct
7	Correct	0 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	880 ms	9324 KB	Output is correct
13	Correct	1082 ms	9708 KB	Output is correct
14	Correct	1621 ms	6764 KB	Output is correct
15	Correct	1948 ms	6380 KB	Output is correct
16	Correct	969 ms	5100 KB	Output is correct
17	Correct	1730 ms	6380 KB	Output is correct
18	Correct	1537 ms	5996 KB	Output is correct
19	Correct	1781 ms	8228 KB	Output is correct
20	Correct	3677 ms	3300 KB	Output is correct
21	Correct	554 ms	876 KB	Output is correct
22	Correct	3988 ms	3692 KB	Output is correct
23	Correct	525 ms	5740 KB	Output is correct
24	Correct	2203 ms	4076 KB	Output is correct
25	Correct	4261 ms	6272 KB	Output is correct
26	Correct	3503 ms	6172 KB	Output is correct
27	Correct	3178 ms	5484 KB	Output is correct
28	Correct	1444 ms	21020 KB	Output is correct
29	Correct	2631 ms	34412 KB	Output is correct
30	Correct	5155 ms	24172 KB	Output is correct
31	Correct	4607 ms	20176 KB	Output is correct
32	Correct	701 ms	10192 KB	Output is correct
33	Correct	1100 ms	10604 KB	Output is correct
34	Correct	719 ms	28112 KB	Output is correct
35	Correct	2618 ms	21556 KB	Output is correct
36	Correct	5246 ms	32156 KB	Output is correct
37	Correct	4175 ms	32492 KB	Output is correct
38	Correct	4235 ms	31908 KB	Output is correct
39	Correct	2029 ms	55040 KB	Output is correct
40	Correct	4555 ms	57032 KB	Output is correct
41	Correct	7891 ms	43160 KB	Output is correct
42	Correct	6895 ms	34332 KB	Output is correct
43	Correct	1583 ms	51820 KB	Output is correct
44	Correct	1110 ms	10860 KB	Output is correct
45	Correct	3456 ms	27432 KB	Output is correct
46	Correct	7047 ms	56044 KB	Output is correct
47	Correct	7126 ms	56036 KB	Output is correct
48	Correct	6901 ms	55524 KB	Output is correct
49	Correct	1 ms	364 KB	Output is correct