oj.uz

Submission #502478

# Submission time Handle Problem Language Result Execution time Memory
502478 2022-01-06T05:43:06 Z khangal Simple game (IZhO17_game) C++14
100 / 100
 272 ms 48740 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];
}
struct str{
    ll sum=0;
}tr[5234567];
void update(ll node,ll l,ll r,ll id,ll delta){
    //cout<<node<<" "<<l<<" "<<r<<" "<<id<<" "<<delta<<'\n';
    if(l > id || r < id)return;
    if(l==r && l==id){
        tr[node].sum += delta;
        return;
    }
    ll mid=(l+r)/2;
    update(node*2 , l,mid , id,delta);
    update(node*2+1 , mid+1 , r , id,delta);
    tr[node].sum = tr[node*2].sum + tr[node*2+1].sum;
}
str query(ll node,ll l,ll r,ll idl,ll idr){
    //cout<<node<<" "<<l<<" "<<r<<" "<<idl<<" "<<idr<<'\n';
    if(l > idr || r < idl){
        str k;
        return k;
    }
    if(l >= idl && r <= idr){
        return tr[node];
    }
    ll mid = (l+r)/2;
    str res;
    str s1,s2;
    s1=query(node*2 , l,mid,idl,idr);
    s2=query(node*2+1 , mid+1,r,idl,idr);
    res.sum = s1.sum+s2.sum;
    return res;
}
class A {
public:
    static void funcA() {
        cin>>n>>m;
        for(int i=1;i<=n;i++){
            cin>>arr[i];
            if(i>1){
                update(1,1,1000000 , min(arr[i-1],arr[i]) ,1);
                update(1,1,1000000 , max(arr[i-1],arr[i])+1 ,-1);
            }
        }
        while(m--){
            ll type;
            cin>>type;
            if(type==1){
                cin>>x>>y;
                if(x==n){
                    update(1,1,1000000 , min(arr[x-1],arr[x]),-1);
                    update(1,1,1000000 , max(arr[x-1],arr[x])+1,1);
                    arr[x]=y;
                    update(1,1,1000000 , min(arr[x-1],arr[x]),1);
                    update(1,1,1000000 , max(arr[x-1],arr[x])+1,-1);
                }
                else{
                    if(x==1){
                        update(1,1,1000000 , min(arr[x+1],arr[x]),-1);
                        update(1,1,1000000 , max(arr[x+1],arr[x])+1,1);
                        arr[x]=y;
                        update(1,1,1000000 , min(arr[x+1],arr[x]),1);
                        update(1,1,1000000 , max(arr[x+1],arr[x])+1,-1);
                    }
                    else{
                        update(1,1,1000000 , min(arr[x-1],arr[x]),-1);
                        update(1,1,1000000 , max(arr[x-1],arr[x])+1,1);
                        update(1,1,1000000 , min(arr[x+1],arr[x]),-1);
                        update(1,1,1000000 , max(arr[x+1],arr[x])+1,1);
                        arr[x]=y;
                        update(1,1,1000000 , min(arr[x-1],arr[x]),1);
                        update(1,1,1000000 , max(arr[x-1],arr[x])+1,-1);
                        update(1,1,1000000 , min(arr[x+1],arr[x]),1);
                        update(1,1,1000000 , max(arr[x+1],arr[x])+1,-1);
                    }
                }
            }
            else{
                cin>>x;
                cout<<query(1,1,1000000,1,x).sum<<'\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 29376 KB Output is correct
2 Correct 21 ms 40800 KB Output is correct
3 Correct 20 ms 40352 KB Output is correct
4 Correct 20 ms 40508 KB Output is correct
5 Correct 20 ms 40524 KB Output is correct
6 Correct 20 ms 40752 KB Output is correct
7 Correct 16 ms 29388 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 29376 KB Output is correct
2 Correct 21 ms 40800 KB Output is correct
3 Correct 20 ms 40352 KB Output is correct
4 Correct 20 ms 40508 KB Output is correct
5 Correct 20 ms 40524 KB Output is correct
6 Correct 20 ms 40752 KB Output is correct
7 Correct 16 ms 29388 KB Output is correct
8 Correct 97 ms 30576 KB Output is correct
9 Correct 172 ms 48660 KB Output is correct
10 Correct 164 ms 48608 KB Output is correct
11 Correct 96 ms 30912 KB Output is correct
12 Correct 127 ms 32584 KB Output is correct
13 Correct 108 ms 32212 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 29376 KB Output is correct
2 Correct 21 ms 40800 KB Output is correct
3 Correct 20 ms 40352 KB Output is correct
4 Correct 20 ms 40508 KB Output is correct
5 Correct 20 ms 40524 KB Output is correct
6 Correct 20 ms 40752 KB Output is correct
7 Correct 16 ms 29388 KB Output is correct
8 Correct 97 ms 30576 KB Output is correct
9 Correct 172 ms 48660 KB Output is correct
10 Correct 164 ms 48608 KB Output is correct
11 Correct 96 ms 30912 KB Output is correct
12 Correct 127 ms 32584 KB Output is correct
13 Correct 108 ms 32212 KB Output is correct
14 Correct 258 ms 48740 KB Output is correct
15 Correct 259 ms 48636 KB Output is correct
16 Correct 255 ms 48680 KB Output is correct
17 Correct 254 ms 48736 KB Output is correct
18 Correct 272 ms 48712 KB Output is correct