oj.uz

Submission #1068528

# Submission time Handle Problem Language Result Execution time Memory
1068528 2024-08-21T10:28:50 Z GrindMachine Game (IOI13_game) C++17
63 / 100
 1188 ms 256000 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/dynamic segtree 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"

struct dynamic_segtree{
    struct node{
        node *l = nullptr, *r = nullptr;
        ll g = 0;
        node(){

        }
        node(ll x){
            g = x;
        }
    };

    node* root;
    int n;

    dynamic_segtree(){

    }

    dynamic_segtree(int n_){
        n = n_;
        root = new node();
    }

    void pupd(node* &u, int lx, int rx, int i, ll v){
        if(!u) u = new node();

        if(rx-lx == 1){
            u->g = v;
            return;
        }

        int mid = (lx+rx) >> 1;

        if(i < mid){
            pupd(u->l,lx,mid,i,v);
        }
        else{
            pupd(u->r,mid,rx,i,v);
        }

        u->g = 0;
        if(u->l) u->g = gcd(u->g,u->l->g);
        if(u->r) u->g = gcd(u->g,u->r->g);
    }

    void pupd(int i, ll v){
        pupd(root,0,n,i,v);
    }

    ll query(node* u, int lx, int rx, int l, int r){
        if(!u) return 0;
        if(lx >= r or rx <= l) return 0;
        if(lx >= l and rx <= r) return u->g;
        int mid = (lx+rx) >> 1;
        return gcd(query(u->l,lx,mid,l,r),query(u->r,mid,rx,l,r));
    }

    ll query(ll l, ll r){
        return query(root,0,n,l,r+1);
    }
};

struct seg2d{
    int n,m;

    struct node{
        node *l = nullptr, *r = nullptr;
        dynamic_segtree st;
        node(int m_){
            st = dynamic_segtree(m_);
        }
    };

    node* root;

    seg2d(){

    }

    seg2d(int n_, int m_){
        n = n_, m = m_;
        root = new node(m);
    }

    void pupd(node* &u, int lx, int rx, int i, int j, ll v){
        if(!u) u = new node(m);

        if(rx-lx == 1){
            u->st.pupd(j,v);
            return;
        }

        int mid = (lx+rx) >> 1;

        if(i < mid){
            pupd(u->l,lx,mid,i,j,v);
        }
        else{
            pupd(u->r,mid,rx,i,j,v);
        }

        ll g = 0;
        if(u->l) g = u->l->st.query(j,j);
        if(u->r) g = gcd(g,u->r->st.query(j,j));

        u->st.pupd(j,g);
    }

    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->st.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);
    }
};

seg2d st;

void init(int n, int m) {
    st = seg2d(n,m);
}

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);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 343 ms 12660 KB Output is correct
5 Correct 230 ms 12852 KB Output is correct
6 Correct 286 ms 9836 KB Output is correct
7 Correct 320 ms 9652 KB Output is correct
8 Correct 241 ms 6736 KB Output is correct
9 Correct 345 ms 9632 KB Output is correct
10 Correct 316 ms 9244 KB Output is correct
11 Correct 1 ms 348 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 515 ms 15796 KB Output is correct
13 Correct 795 ms 6468 KB Output is correct
14 Correct 180 ms 1076 KB Output is correct
15 Correct 858 ms 8876 KB Output is correct
16 Correct 155 ms 18260 KB Output is correct
17 Correct 569 ms 11600 KB Output is correct
18 Correct 861 ms 18540 KB Output is correct
19 Correct 736 ms 18704 KB Output is correct
20 Correct 685 ms 18172 KB Output is correct
21 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 330 ms 12760 KB Output is correct
13 Correct 232 ms 12880 KB Output is correct
14 Correct 297 ms 9852 KB Output is correct
15 Correct 330 ms 9556 KB Output is correct
16 Correct 218 ms 6740 KB Output is correct
17 Correct 319 ms 9764 KB Output is correct
18 Correct 274 ms 9264 KB Output is correct
19 Correct 553 ms 15956 KB Output is correct
20 Correct 718 ms 6072 KB Output is correct
21 Correct 166 ms 848 KB Output is correct
22 Correct 879 ms 8820 KB Output is correct
23 Correct 164 ms 18388 KB Output is correct
24 Correct 574 ms 11604 KB Output is correct
25 Correct 912 ms 18500 KB Output is correct
26 Correct 774 ms 18764 KB Output is correct
27 Correct 719 ms 18256 KB Output is correct
28 Correct 688 ms 256000 KB Output is correct
29 Runtime error 1188 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 352 KB Output is correct
6 Correct 1 ms 356 KB Output is correct
7 Correct 1 ms 396 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 352 KB Output is correct
10 Correct 1 ms 352 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 343 ms 12592 KB Output is correct
13 Correct 252 ms 12988 KB Output is correct
14 Correct 297 ms 9808 KB Output is correct
15 Correct 330 ms 9552 KB Output is correct
16 Correct 225 ms 6744 KB Output is correct
17 Correct 316 ms 9808 KB Output is correct
18 Correct 290 ms 9416 KB Output is correct
19 Correct 494 ms 15952 KB Output is correct
20 Correct 709 ms 6240 KB Output is correct
21 Correct 167 ms 848 KB Output is correct
22 Correct 813 ms 8868 KB Output is correct
23 Correct 151 ms 18260 KB Output is correct
24 Correct 508 ms 11600 KB Output is correct
25 Correct 793 ms 18572 KB Output is correct
26 Correct 716 ms 18736 KB Output is correct
27 Correct 654 ms 18212 KB Output is correct
28 Correct 624 ms 256000 KB Output is correct
29 Runtime error 1175 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -