| # |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
| 141694 |
2019-08-08T22:24:51 Z |
liwi |
게임 (IOI13_game) |
C++11 |
|
3 ms |
376 KB |
#include "game.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;
#define complete_unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define all(a) a.begin(),a.end()
#define println printf("\n");
#define readln(x) getline(cin,x);
#define pb push_back
#define endl "\n"
#define INT_INF 0x3f3f3f3f
#define LL_INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define mp make_pair
#define fastio cin.tie(0); cin.sync_with_stdio(0);
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
typedef unordered_map<int,int> umii;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef pair<int,pii> triple;
typedef int8_t byte;
mt19937 g1(time(0));
int randint(int a, int b){return uniform_int_distribution<int>(a, b)(g1);}
ll randlong(ll a,ll b){return uniform_int_distribution<long long>(a, b)(g1);}
ll gcd(ll a, ll b){return b == 0 ? a : gcd(b, a % b);}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
ll fpow(ll b, ll exp, ll mod){if(exp == 0) return 1;ll t = fpow(b,exp/2,mod);if(exp&1) return t*t%mod*b%mod;return t*t%mod;}
ll divmod(ll i, ll j, ll mod){i%=mod,j%=mod;return i*fpow(j,mod-2,mod)%mod;}
template<typename T>
struct node{
T val; int sz; ll prior,gg;
node *l,*r;
node(T v){
val = v, sz = 1, gg = val.second;
prior = randlong(1,1e18);
l = r = 0;
}
};
template<typename T>
struct SMTreap{
node<T> *rt=0;
inline int gsz(node<T> *&n){return n?n->sz:0;}
inline void upd_sz(node<T> *&n){if(n)n->sz=gsz(n->l)+gsz(n->r)+1;}
inline ll ggcd(node<T> *&n){return n?n->gg:0;}
inline void upd_gcd(node<T> *&n){if(n)n->gg=__gcd(__gcd(ggcd(n->l),ggcd(n->r)),n->val.second);}
inline void upd(node<T> *&n){upd_sz(n);upd_gcd(n);}
void split(node<T> *n, T key, node<T> *&l, node<T> *&r){
if(!n) l = r = 0;
else if(key < n->val) split(n->l,key,l,n->l), r = n;
else split(n->r,key,n->r,r), l = n;
upd(n);
}
void merge(node<T> *&n, node<T> *l, node<T> *r){
if(!l || !r) n = l?l:r;
else if(l->prior > r->prior) merge(l->r,l->r,r), n = l;
else merge(r->l,l,r->l), n = r;
upd(n);
}
void insert(node<T> *&n, node<T> *v){
if(!n) n = v;
else if(v->prior > n->prior) split(n,v->val,v->l,v->r), n = v;
else insert(v->val<n->val?n->l:n->r,v);
upd(n);
}
void replace(node<T> *&n, int idx, ll v){
if(!n) assert(false);
if(n->val.first == idx) n->val.second = v;
else replace(n->val.first<idx?n->r:n->l,idx,v);
upd(n);
}
void erase(node<T> *&n, T v){
if(!n) return;
if(n->val == v) merge(n,n->l,n->r);
else erase(v<n->val?n->l:n->r,v);
upd(n);
}
T kth(node<T> *&n, int idx){
if(gsz(n->l)+1 == idx) return n->val;
else if(gsz(n->l) >= idx) return kth(n->l,idx);
return kth(n->r,idx-gsz(n->l)-1);
}
ll range_query(int l, int r){
if(!rt) return 0;
node<T> *t1=0,*t2=0,*t3=0;
split(rt,mp(l,-1),t1,t2);
split(t2,mp(r+1,-1),t2,t3);
ll ans = ggcd(t2);
merge(rt,t1,t2);
merge(rt,rt,t3);
return ans;
}
void print(){
for(int i=1; i<=gsz(rt); i++)
printf("%d ",find_by_order(rt,i));
printf("\n");
}
};
struct snode{
int l,r;
SMTreap<pair<int,ll>> s;
snode *lft,*rgt;
snode(int l, int r){
this->l = l;
this->r = r;
lft = rgt = 0;
}
void update(int row, int col, ll val, int ins){
if(ins) s.insert(s.rt,new node<pair<int,ll>>(mp(col,val)));
else s.replace(s.rt,col,val);
if(l == r) return;
int mid = (l+r)/2;
if(row <= mid){
if(!lft) lft = new snode(l,mid);
lft->update(row,col,val,ins);
}else{
if(!rgt) rgt = new snode(mid+1,r);
rgt->update(row,col,val,ins);
}
}
ll query(int rl, int rr, int cl, int cr){
if(l == rl && r == rr) return s.range_query(cl,cr);
int mid = (l+r)/2;
if(rr <= mid){
if(!lft) return 0;
return lft->query(rl,rr,cl,cr);
}else if(rl > mid){
if(!rgt) return 0;
return rgt->query(rl,rr,cl,cr);
}else{
ll f = !lft?0:lft->query(rl,mid,cl,cr);
ll s = !rgt?0:rgt->query(mid+1,rr,cl,cr);
return __gcd(f,s);
}
}
};
int num_rows,num_cols;
set<pii> s;
snode *seg;
void init(int R, int C){
num_rows = R, num_cols = C;
seg = new snode(1,R);
}
void update(int P, int Q, ll K){
P++, Q++;
seg->update(P,Q,K,!s.count(mp(P,Q)));
s.insert(mp(P,Q));
}
ll calculate(int r1, int c1, int r2, int c2){
r1++, c1++, r2++, c2++;
return seg->query(r1,r2,c1,c2);
}
void print(){
for(int i=1; i<=num_rows; i++){
for(int k=1; k<=num_cols; k++)
printf("%lld ",seg->query(i,i,k,k));
printf("\n");
}
printf("\n");
}
Compilation message
grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
int res;
^~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
376 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
376 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
376 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
256 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
376 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
376 KB |
Output is correct |
| 3 |
Correct |
3 ms |
368 KB |
Output is correct |
| 4 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
