oj.uz

Submission #332978

# Submission time Handle Problem Language Result Execution time Memory
332978 2020-12-04T06:29:58 Z gmyu Game (IOI13_game) C++11
63 / 100
 1974 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

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

/// use Treap-like concept to
struct NODEY {
    NODEY *lp, *rp;     // left ptr, right ptr
    ll g, val;
    NODEY() : lp(NULL), rp(NULL), g(0LL), val(0LL) {}
};
int NYseg[2];

void pullY(NODEY *pny) {
    ll g1 = (!pny->lp) ? 0LL : pny->lp->g;
    ll g2 = (!pny->rp) ? 0LL : pny->rp->g;
    pny->g = gcd2(gcd2(g1, g2), pny->val);
}
void updY(int vty, ll val, NODEY *pny, int l = NYseg[0], int r = NYseg[1]){
    if(!pny) pny = new NODEY();
    if(l == r) { pny->g = val; pny->val = val; return; } // leaf

    int mid = (l + r) / 2;
    if(vty == mid) {
        pny->val = val;
    } else if (vty < mid) {
        if(mid-1 >= l) {
            if(!pny->lp) pny->lp = new NODEY();
            updY(vty, val, pny->lp, l, mid -1);
        }
    } else {
        if(mid+1 <= r) {
            if(!pny->rp) pny->rp = new NODEY();
            updY(vty, val, pny->rp, mid+1, r);
        }
    }

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

    int mid = (l + r) / 2;
    ll g1 = (!pny->lp) ? 0LL : ( (mid-1 >= l) ? queY(qle, qri, pny->lp, l, mid-1) : 0LL );
    ll g2 = (!pny->rp) ? 0LL : ( (mid+1 <= r) ? queY(qle, qri, pny->rp, mid+1, r) : 0LL );
    ll g3 = (qle <= mid && mid <= qri) ? pny->val : 0LL;
    return gcd2(gcd2(g1, g2), g3);
}

struct NODEX {
    NODEX *lp, *rp;     // left ptr, right ptr
    NODEY *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(!pnx->pny) pnx->pny = new NODEY();
    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 (!pnx->pny) ? 0LL : 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 1 ms 364 KB Output is correct
3 Correct 1 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 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 554 ms 13932 KB Output is correct
5 Correct 527 ms 14188 KB Output is correct
6 Correct 657 ms 11688 KB Output is correct
7 Correct 722 ms 11372 KB Output is correct
8 Correct 438 ms 8172 KB Output is correct
9 Correct 711 ms 11372 KB Output is correct
10 Correct 659 ms 10988 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 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 0 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 364 KB Output is correct
12 Correct 1089 ms 16876 KB Output is correct
13 Correct 1653 ms 7020 KB Output is correct
14 Correct 306 ms 1900 KB Output is correct
15 Correct 1950 ms 9836 KB Output is correct
16 Correct 264 ms 20076 KB Output is correct
17 Correct 982 ms 13296 KB Output is correct
18 Correct 1693 ms 20324 KB Output is correct
19 Correct 1404 ms 20588 KB Output is correct
20 Correct 1324 ms 20076 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 364 KB Output is correct
3 Correct 1 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 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 551 ms 14012 KB Output is correct
13 Correct 526 ms 14188 KB Output is correct
14 Correct 620 ms 11584 KB Output is correct
15 Correct 734 ms 11476 KB Output is correct
16 Correct 437 ms 8172 KB Output is correct
17 Correct 708 ms 11372 KB Output is correct
18 Correct 659 ms 11116 KB Output is correct
19 Correct 1089 ms 16620 KB Output is correct
20 Correct 1708 ms 6764 KB Output is correct
21 Correct 308 ms 1772 KB Output is correct
22 Correct 1974 ms 9896 KB Output is correct
23 Correct 262 ms 19948 KB Output is correct
24 Correct 934 ms 13292 KB Output is correct
25 Correct 1655 ms 20588 KB Output is correct
26 Correct 1386 ms 20716 KB Output is correct
27 Correct 1325 ms 20076 KB Output is correct
28 Runtime error 846 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 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 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 384 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 364 KB Output is correct
12 Correct 565 ms 14956 KB Output is correct
13 Correct 557 ms 15232 KB Output is correct
14 Correct 649 ms 12652 KB Output is correct
15 Correct 764 ms 12396 KB Output is correct
16 Correct 452 ms 9068 KB Output is correct
17 Correct 718 ms 12396 KB Output is correct
18 Correct 691 ms 12012 KB Output is correct
19 Correct 1106 ms 17644 KB Output is correct
20 Correct 1668 ms 8044 KB Output is correct
21 Correct 310 ms 2900 KB Output is correct
22 Correct 1974 ms 10816 KB Output is correct
23 Correct 257 ms 20972 KB Output is correct
24 Correct 970 ms 14316 KB Output is correct
25 Correct 1743 ms 21444 KB Output is correct
26 Correct 1456 ms 21484 KB Output is correct
27 Correct 1394 ms 21136 KB Output is correct
28 Runtime error 822 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -