oj.uz

Submission #502554

# Submission time Handle Problem Language Result Execution time Memory
502554 2022-01-06T08:37:52 Z khangal Simple game (IZhO17_game) C++14
100 / 100
 156 ms 40140 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef double db;
typedef vector<long long> vl;
typedef pair<long long, long long > pl;
const int N = 1e6 + 1;
#define po pop_back
#define pb push_back
#define mk make_pair
#define lw lower_bound
#define up upper_bound
#define ff first
#define ss second
#define boost ios_base::sync_with_stdio(); cin.tie(0); cout.tie(0);
#define MOD 1000000007
#define MAX 1e18 
#define MIN -1e18
#define per(i,a,b) for(ll i=b;i>=a;i--)
#define con continue
#define freopen freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define PI 3.14159265358979323846264338327950288419716939937510582097494459230781640628
//typedef tree<ll , null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
template< typename T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll n, m, ans, mid, mn, mx, cnt, sum, h1, h2, arr[3234567],arr1[1234567], sz, k, i, j, h, a, w, x, y, z,par[1234567];
bool used[1234567];
ll dx[4]={-1,1,0,0},dy[4]={0,0,-1,1},c1[123][123];
vector<ll> edge[1234567];
ll jump[22][223456];
ll lvl[1234567];
//ll bit[1234567];
//ll timer;
//ll st[1234567],endd[1234567];
//ll dp[5005][5005];
ll power(ll base, ll val, ll mod) {
    ll res = 1;
    while (val) {
        if (val % 2 == 1) {
            res = res * base;
        }
        base = base * base;
        base %= mod;
        res %= mod;
        val /= 2;
    }
    return res;
}
bool comp(pl x,pl y){
    if(x.ff>y.ff)return true;
    return false;
}
ll find(ll x){
    if(x==par[x])return x;
    else return par[x]=find(par[x]);
}
void process_LCA(){
    for(int i=1;(1<<i)<=n;i++){
        for(int j=1;j<=n;j++){
            jump[i][j] = jump[i-1][jump[i-1][j]];
        }
    }
}
ll LCA(ll x,ll y){
    if(lvl[x] < lvl[y])swap(x,y);
    ll diss = lvl[x] - lvl[y];
    for(int i=21;i>=0;i--){
        if((1<<i)&diss){
            x = jump[i][x];
        }
    }
    if(x==y)return x;
    for(int i=21;i>=0;i--){
        if(jump[i][x] != jump[i][y]){
            x = jump[i][x];
            y = jump[i][y];
        }
    }
    return jump[0][x];
}
ll tr[5234567];
void update(ll x,ll val){
    while(x<=1000000){
        tr[x]+=val;
        //cout<<x<<'\n';
        x += (x&-x);
    }
}
ll query(ll x){
    ll res=0;
    while(x>0){
        res+=tr[x];
        x -= (x&-x);
    }
    return res;
}
class A {
public:
    static void funcA() {
        cin>>n>>k;
        for(int i=1;i<=n;i++){
            cin>>arr[i];
        }
        for(int i=2;i<=n;i++){            
            update(min(arr[i-1],arr[i]),1);
            update(max(arr[i-1],arr[i])+1,-1);
        }
        while(k--){
            ll type;
            cin>>type;
            if(type==1){
                cin>>x>>y;
                if(x!=1)
                {update(min(arr[x-1],arr[x]),-1);
                update(max(arr[x-1],arr[x])+1,1);}
                if(x!=n){
                update(max(arr[x+1],arr[x])+1,1);
                update(min(arr[x+1],arr[x]),-1);}
                arr[x]=y;
                if(x!=1){
                update(min(arr[x-1],arr[x]),1);
                update(max(arr[x-1],arr[x])+1,-1);}
                if(x!=n){
                update(max(arr[x+1],arr[x])+1,-1);
                update(min(arr[x+1],arr[x]),1);}
            }
            else{
                cin>>x;
                cout<<query(x)<<'\n';
            }
        }
    }
}lol;
void solve() {
    A::funcA();
}
int main() {
    ll T = 1;
    //cin>>T;
    boost;
    while (T--) {
        solve();
    }
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 29276 KB Output is correct
2 Correct 19 ms 35832 KB Output is correct
3 Correct 19 ms 35576 KB Output is correct
4 Correct 21 ms 35756 KB Output is correct
5 Correct 19 ms 35572 KB Output is correct
6 Correct 22 ms 35832 KB Output is correct
7 Correct 19 ms 29400 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 29276 KB Output is correct
2 Correct 19 ms 35832 KB Output is correct
3 Correct 19 ms 35576 KB Output is correct
4 Correct 21 ms 35756 KB Output is correct
5 Correct 19 ms 35572 KB Output is correct
6 Correct 22 ms 35832 KB Output is correct
7 Correct 19 ms 29400 KB Output is correct
8 Correct 71 ms 31064 KB Output is correct
9 Correct 103 ms 40088 KB Output is correct
10 Correct 125 ms 40140 KB Output is correct
11 Correct 67 ms 30984 KB Output is correct
12 Correct 90 ms 32260 KB Output is correct
13 Correct 90 ms 32160 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 29276 KB Output is correct
2 Correct 19 ms 35832 KB Output is correct
3 Correct 19 ms 35576 KB Output is correct
4 Correct 21 ms 35756 KB Output is correct
5 Correct 19 ms 35572 KB Output is correct
6 Correct 22 ms 35832 KB Output is correct
7 Correct 19 ms 29400 KB Output is correct
8 Correct 71 ms 31064 KB Output is correct
9 Correct 103 ms 40088 KB Output is correct
10 Correct 125 ms 40140 KB Output is correct
11 Correct 67 ms 30984 KB Output is correct
12 Correct 90 ms 32260 KB Output is correct
13 Correct 90 ms 32160 KB Output is correct
14 Correct 140 ms 40060 KB Output is correct
15 Correct 148 ms 40056 KB Output is correct
16 Correct 132 ms 40076 KB Output is correct
17 Correct 156 ms 40128 KB Output is correct
18 Correct 131 ms 40028 KB Output is correct