| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 332961 |
2020-12-04T04:43:48 Z |
gmyu |
Game (IOI13_game) |
C++14 |
|
1 ms |
492 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 );
return gcd2(gcd2(g1, g2), ny[v].val);
}
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);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
Incorrect |
1 ms |
364 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
492 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
