oj.uz

Submission #332008

# Submission time Handle Problem Language Result Execution time Memory
332008 2020-12-01T08:07:21 Z hackxsaras Game (IOI13_game) C++14
10 / 100
 13000 ms 3908 KB 
#include <bits/stdc++.h>
#include <chrono> 
#include <game.h>
using namespace std;
using namespace std::chrono; 
 
// #pragma GCC target ("avx2")
// #pragma GCC optimization ("O3")
// #pragma GCC optimization ("unroll-loops")
// #pragma optimization_level 3
// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define pb push_back
#define galen_colin {ios_base::sync_with_stdio(false);}
#define orz {cin.tie(NULL); cout.tie(NULL);}
#define fix(prec) {cout << setprecision(prec) << fixed;}
#define mp make_pair
#define f first
#define s second
#define all(v) v.begin(), v.end()

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pii> vpi;
typedef vector<pll> vpl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;

template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v);
template<typename A, typename B> ostream& operator<<(ostream &cout, pair<A, B> const &p) { return cout << "(" << p.f << ", " << p.s << ")"; }
template<typename A> ostream& operator<<(ostream &cout, vector<A> const &v) {
    cout << ""; for(int i = 0; i < v.size(); i++) {if (i) cout << " "; cout << v[i];} return cout << "\n";
}
template<typename A, typename B> istream& operator>>(istream& cin, pair<A, B> &p) {
    cin >> p.first;
    return cin >> p.second;
}
template<typename A> istream& operator>>(istream& cin, vector<A> &v) {
    for(auto &x:v)cin>>x;
    return cin;
}

ll min(ll a, int b){return min(a, (ll) b);}
ll min(int a, ll b){return min(b, (ll) a);}
ll max(ll a, int b){return max(a, (ll) b);}
ll max(int a, ll b){return max(b, (ll) a);}

void usaco(string filename) {
  // #pragma message("be careful, freopen may be wrong")
    freopen((filename + ".in").c_str(), "r", stdin);
    freopen((filename + ".out").c_str(), "w", stdout);
}
 
const ld pi = 3.14159265358979323846;
const ll mod = 1000000007;
// const ll mod = 998244353;
// ll mod;
const ll INF = 1e9+7;
 #include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 



ll n, m, k, q, l, r, x, y, z;

class chash { 
public: 
    size_t operator()(const pair<pii,pii> &p) const
    { 
        return (p.f.f) ^ (p.f.s) ^ (p.s.f) ^ (p.s.s);
    } 
}; 

cc_hash_table<pair<pair<int,int>, pair<int,int>>, ll, chash> segtree;

ll __gcd(ll &p, ll& q, ll& r, ll &s){
	//cout<<p<<" "<<q<<" "<<r<<" "<<s<<" = "<<__gcd(p, __gcd(q, __gcd(r, s)))<<"\n";
	return __gcd(p, __gcd(q, __gcd(r, s))) ;
}
void init(int r, int c){
	n = r, m = c;
}
ll update(int sx, int sy, int ex, int ey, int& a, int& b, ll& k){
	if(sx > ex || sy > ey) return 0;
	if(a > ex || a < sx || b > ey || b < sy){
		auto it = segtree.find({{sx, sy}, {ex, ey}});
		if(it != segtree.end()) return (*it).s;
		return 0;
	}
	if(sx == ex && sy == ey){
		return segtree[{{sx,sy}, {ex, ey}}] = k;
	}

	int mx = (sx + ex)/2,
	    my = (sy + ey)/2;

	ll p = update(sx,sy,mx,my,a,b,k),
	   q = update(sx,my+1,mx,ey,a,b,k),
	   r = update(mx+1,sy,ex,my,a,b,k),
	   s = update(mx+1,my+1,ex,ey,a,b,k);

	return segtree[{{sx, sy},{ex, ey}}] = __gcd(p,q,r,s);
}
void update(int a, int b, ll k){
	update(0, 0, n-1, m-1, a, b, k);
}
ll calculate(int sx,int sy, int ex, int ey, int& rsx, int& rsy, int& rex, int& rey){
	if(sx > ex || sy > ey) return 0;
	if(rsx > ex || rex < sx || rsy > ey || rey < sy) return 0;

	if(sx >= rsx && sy >= rsy && ex<=rex && ey<=rey){
		auto it = segtree.find({{sx, sy}, {ex, ey}});
		if(it != segtree.end()) return (*it).s;
		return 0;
	}

	int mx = (sx + ex)/2,
	    my = (sy + ey)/2;

	ll p = calculate(sx,sy,mx,my,rsx, rsy, rex, rey),
	   q = calculate(sx,my+1,mx,ey,rsx, rsy, rex, rey),
	   r = calculate(mx+1,sy,ex,my,rsx, rsy, rex, rey),
	   s = calculate(mx+1,my+1,ex,ey,rsx, rsy, rex, rey);

	return __gcd(p,q,r,s);
}


/*
20 6 15
0 14 0

0 0 1 2 = 14
0 0 0 1 = 6
0 2 0 2 = 15
1 0 1 1 = 14
1 2 1 2 = 0
*/
ll calculate(int sx, int sy, int ex, int ey){
	return calculate(0, 0, n-1, m-1, sx, sy, ex, ey);
}
//  void showall(){

//     // for(int i=0;i<n;i++){
//     // 	for(int j=0;j<m;j++){
//     // 		cout<<segtree[{{i,j},{i,j}}]<<" ";
//     // 	}
//     // 	cout<<"\n";
//     // }
//  }
// int main() {
//     init(2,3);
//     update(0,0,20); showall();
//     update(0,2,15); showall();
//     update(1,1,12); showall();
//     cout<<calculate(0,0,0,2)<<"\n";
//     cout<<calculate(0,0,1,1)<<"\n";
//     update(0,1,6); showall();
//     update(1,1,14); showall();
//     cout<<calculate(0,0,0,2)<<"\n";
//     cout<<calculate(0,0,1,1)<<"\n";
// }

Compilation message

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

Subtask #2
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 Execution timed out 13051 ms 3908 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 4 ms 364 KB Output is correct
3 Correct 3 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 2 ms 364 KB Output is correct
12 Execution timed out 13052 ms 1224 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 4 ms 364 KB Output is correct
3 Correct 3 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 2 ms 364 KB Output is correct
12 Execution timed out 13075 ms 3772 KB Time limit exceeded
13 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 6 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 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 2 ms 364 KB Output is correct
12 Execution timed out 13086 ms 3768 KB Time limit exceeded
13 Halted 0 ms 0 KB -