oj.uz

Submission #332919

# Submission time Handle Problem Language Result Execution time Memory
332919 2020-12-04T02:00:28 Z gmyu Game (IOI13_game) C++14
63 / 100
 2059 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;
}


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

    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);
    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 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 0 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 580 ms 13908 KB Output is correct
5 Correct 594 ms 14164 KB Output is correct
6 Correct 618 ms 10964 KB Output is correct
7 Correct 724 ms 9944 KB Output is correct
8 Correct 428 ms 6492 KB Output is correct
9 Correct 669 ms 10196 KB Output is correct
10 Correct 698 ms 9940 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 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 938 ms 11616 KB Output is correct
13 Correct 1534 ms 4700 KB Output is correct
14 Correct 295 ms 1036 KB Output is correct
15 Correct 1789 ms 5064 KB Output is correct
16 Correct 248 ms 16840 KB Output is correct
17 Correct 828 ms 9940 KB Output is correct
18 Correct 1387 ms 17352 KB Output is correct
19 Correct 1167 ms 18320 KB Output is correct
20 Correct 1102 ms 17608 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 576 ms 13780 KB Output is correct
13 Correct 587 ms 14312 KB Output is correct
14 Correct 622 ms 11092 KB Output is correct
15 Correct 722 ms 9812 KB Output is correct
16 Correct 425 ms 6492 KB Output is correct
17 Correct 680 ms 10324 KB Output is correct
18 Correct 701 ms 9940 KB Output is correct
19 Correct 961 ms 11348 KB Output is correct
20 Correct 1568 ms 4572 KB Output is correct
21 Correct 293 ms 1004 KB Output is correct
22 Correct 1853 ms 5104 KB Output is correct
23 Correct 255 ms 16840 KB Output is correct
24 Correct 820 ms 9884 KB Output is correct
25 Correct 1495 ms 17408 KB Output is correct
26 Correct 1210 ms 18016 KB Output is correct
27 Correct 1126 ms 17480 KB Output is correct
28 Correct 962 ms 134732 KB Output is correct
29 Runtime error 2059 ms 256004 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 512 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 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 590 ms 13848 KB Output is correct
13 Correct 596 ms 14180 KB Output is correct
14 Correct 663 ms 10836 KB Output is correct
15 Correct 770 ms 9812 KB Output is correct
16 Correct 450 ms 6548 KB Output is correct
17 Correct 670 ms 10196 KB Output is correct
18 Correct 670 ms 10060 KB Output is correct
19 Correct 967 ms 11508 KB Output is correct
20 Correct 1572 ms 4624 KB Output is correct
21 Correct 305 ms 1004 KB Output is correct
22 Correct 1793 ms 5044 KB Output is correct
23 Correct 235 ms 16840 KB Output is correct
24 Correct 845 ms 9812 KB Output is correct
25 Correct 1456 ms 17320 KB Output is correct
26 Correct 1208 ms 18140 KB Output is correct
27 Correct 1127 ms 17480 KB Output is correct
28 Correct 906 ms 134748 KB Output is correct
29 Runtime error 2009 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -