Submission #502478

#TimeUsernameProblemLanguageResultExecution timeMemory
502478khangalSimple game (IZhO17_game)C++14
100 / 100
272 ms48740 KiB
#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(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...