oj.uz

Submission #332007

# Submission time Handle Problem Language Result Execution time Memory
332007 2020-12-01T07:49:48 Z hackxsaras Game (IOI13_game) C++14
37 / 100
 13000 ms 13944 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;
 


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

map<pair<pair<int,int>, pair<int,int>>, ll> 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 384 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 384 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 2 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 6185 ms 13648 KB Output is correct
5 Correct 4339 ms 13432 KB Output is correct
6 Correct 3028 ms 11120 KB Output is correct
7 Correct 3656 ms 10716 KB Output is correct
8 Correct 2037 ms 9104 KB Output is correct
9 Correct 3485 ms 10860 KB Output is correct
10 Correct 3362 ms 10860 KB Output is correct
11 Correct 1 ms 376 KB Output is correct

Subtask #3
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 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 Execution timed out 13090 ms 2612 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 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 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 Correct 5959 ms 13420 KB Output is correct
13 Correct 4405 ms 13508 KB Output is correct
14 Correct 2951 ms 11032 KB Output is correct
15 Correct 3485 ms 10732 KB Output is correct
16 Correct 2017 ms 8940 KB Output is correct
17 Correct 3243 ms 10888 KB Output is correct
18 Correct 3374 ms 10608 KB Output is correct
19 Execution timed out 13020 ms 2496 KB Time limit exceeded
20 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 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 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 Correct 5973 ms 13944 KB Output is correct
13 Correct 4383 ms 13472 KB Output is correct
14 Correct 2986 ms 11176 KB Output is correct
15 Correct 3528 ms 11136 KB Output is correct
16 Correct 2033 ms 9088 KB Output is correct
17 Correct 3301 ms 10988 KB Output is correct
18 Correct 3386 ms 10608 KB Output is correct
19 Execution timed out 13004 ms 2680 KB Time limit exceeded
20 Halted 0 ms 0 KB -