| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1068117 |
2024-08-21T07:48:43 Z |
GrindMachine |
Game (IOI13_game) |
C++17 |
|
1 ms |
436 KB |
#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;
template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl
#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)
template<typename T>
void amin(T &a, T b) {
a = min(a,b);
}
template<typename T>
void amax(T &a, T b) {
a = max(a,b);
}
#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif
/*
already knew the solution idea (dynamic segtree with a treap in each node)
*/
const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;
#include "game.h"
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct node{
node *l = nullptr, *r = nullptr;
int siz = 0;
unsigned int prior = 0;
bool flip = 0;
int p = 0, mxp = 0;
ll val = 0, g = 0;
node(int i, ll v){
l = r = nullptr;
siz = 1;
prior = rng();
flip = 0;
p = i, mxp = i, val = v, g = v;
}
void recalc(){
siz = 1, mxp = p, g = val;
if(l) siz += l->siz, amax(mxp,l->mxp), g = gcd(g,l->g);
if(r) siz += r->siz, amax(mxp,r->mxp), g = gcd(g,r->g);
}
void prop(){
if(!flip) return;
swap(l,r);
if(l) l->flip ^= 1;
if(r) r->flip ^= 1;
flip = 0;
}
~node(){
delete l;
delete r;
l = r = nullptr;
}
};
node* merge(node* u, node* v){
if(u) u->prop();
if(v) v->prop();
if(u == nullptr) return v;
if(v == nullptr) return u;
if(u->prior > v->prior){
// v goes to u's right subtree
u->r = merge(u->r,v);
u->recalc();
return u;
}
else{
// u goes to v's left subtree
v->l = merge(u,v->l);
v->recalc();
return v;
}
}
pair<node*,node*> split(node* u, int k){
if(!u) return {nullptr,nullptr};
u->prop();
if(k == 0) return {nullptr,u};
if(k == u->siz) return {u,nullptr};
int pos = 1;
if(u->l) pos += u->l->siz;
if(k < pos){
// required pos lies in the left subtree
// root belongs to the right subtree
auto p = split(u->l,k);
u->l = p.ss;
u->recalc();
return {p.ff,u};
}
else{
// required pos lies in the right subtree
// root belongs to the left subtree
auto p = split(u->r,k-pos);
u->r = p.ff;
u->recalc();
return {u,p.ss};
}
}
int lb(node* u, int i){
// first ind s.t pos >= i (inds start from 1)
if(u->l and u->l->mxp >= i){
return lb(u->l,i);
}
int add = (u->l?u->l->siz:0);
if(u->p >= i){
return add+1;
}
if(u->r){
return lb(u->r,i)+add+1;
}
else{
return add+2;
}
}
int ub(node* u, int i){
return lb(u,i+1);
}
vector<node*> split_many(node* treap, vector<int> cuts){
vector<node*> parts;
rev(i,sz(cuts)-1,0){
auto p = split(treap,cuts[i]);
treap = p.ff;
parts.pb(p.ss);
}
parts.pb(treap);
reverse(all(parts));
return parts;
}
node* merge_many(vector<node*> parts){
node* treap = nullptr;
trav(part,parts){
treap = merge(treap,part);
}
return treap;
}
struct dynamic_treap{
node* treap = new node(0,0);
void pupd(int i, ll v){
int pos = ub(treap,i);
auto parts = split_many(treap,{pos-1});
if(parts[0] and parts[0]->mxp == i){
auto new_parts = split_many(parts[0],{parts[0]->siz-1});
parts[0] = new_parts[0];
}
parts.insert(parts.begin()+1,new node(i,v));
treap = merge_many(parts);
}
ll query(int l, int r){
l = lb(treap,l);
r = ub(treap,r)-1;
if(l > r) return 0ll;
auto parts = split_many(treap,{l-1,r});
ll res = parts[1]->g;
treap = merge_many(parts);
return res;
}
};
struct dynamic_segtree{
struct node{
node *l = nullptr, *r = nullptr;
dynamic_treap treap;
node(){
}
};
node* root;
int n;
dynamic_segtree(){
}
dynamic_segtree(int n_){
root = new node();
n = n_;
}
void pupd(node* &u, int lx, int rx, int i, int j, ll v){
u->treap.pupd(j,v);
if(rx-lx == 1) return;
int mid = (lx+rx) >> 1;
if(!u->l) u->l = new node();
if(!u->r) u->r = new node();
if(i < mid){
pupd(u->l,lx,mid,i,j,v);
}
else{
pupd(u->r,mid,rx,i,j,v);
}
}
void pupd(int i, int j, ll v){
pupd(root,0,n,i,j,v);
}
ll query(node* u, int lx, int rx, int l, int r, int x, int y){
if(!u) return 0;
if(lx >= r or rx <= l) return 0;
if(lx >= l and rx <= r) return u->treap.query(x,y);
int mid = (lx+rx) >> 1;
return gcd(query(u->l,lx,mid,l,r,x,y),query(u->r,mid,rx,l,r,x,y));
}
ll query(int l, int r, int x, int y){
return query(root,0,n,l,r+1,x,y);
}
};
dynamic_segtree st;
void init(int n, int m) {
st = dynamic_segtree(n);
}
void update(int i, int j, long long v) {
st.pupd(i,j,v);
}
long long calculate(int l1, int l2, int r1, int r2) {
return st.query(l1,r1,l2,r2);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
436 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
