oj.uz

답안 #1118347

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1118347 2024-11-25T11:10:30 Z Younis_Dwai Simple game (IZhO17_game) C++14
0 / 100
 3 ms 10844 KB 
//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#define endl "\n"
#define F first
#define S second
#define pb push_back
//#define int long long
#define in insert
#define mid (l+r)/2
#define in insert
using namespace std;
const int N=1e5+6;
int tree[N*40],b[N],n,m;
void upd(int node , int l , int r , int s,int e, int v){
     //cout<<" # "<<node<<' '<<l<<' '<<r<<endl;
     if(l>=s && r<=e){
        tree[node]+=v;
        return ;
     }
     else if(l>e || r<s) return ;
     upd(node*2,l,mid,s,e,v);
     upd(node*2+1,mid+1,r,s,e,v);
     return ;
}
int query(int node , int l , int r , int id){
    if(l>id || r<id) return 0;
    else if(l==r) return tree[node];
    return tree[node]+query(node*2,l,mid,id)+query(node*2+1,mid+1,r,id);
}
void modify(int id , int val){
     if(id+1<=n){
        upd(1,1,1e6,min(b[id],b[id+1]),max(b[id],b[id+1]),-1);
        upd(1,1,1e6,min(val,b[id+1]),max(val,b[id+1]),1);
     }
     if(id-1>=1){
        upd(1,1,1e6,min(b[id],b[id-1]),max(b[id],b[id-1]),-1);
        upd(1,1,1e6,min(val,b[id-1]),max(val,b[id-1]),1);
     }
     return ;
}
int32_t main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>b[i];
    for(int i=1;i<n;i++){
        int l=min(b[i],b[i+1]),r=max(b[i],b[i+1]);
        upd(1,1,1e6,l,r,1);
    }
    for(int i=1;i<=m;i++){
        int op;cin>>op;
        if(op==1){
           int pos,val;
           cin>>pos>>val;
           modify(pos,val);
        }
        else{
           int id;cin>>id;
           cout<<query(1,1,1e6,id)<<endl;
        }
    }
    return 0;
}

Subtask #1
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Incorrect 3 ms 10844 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Incorrect 3 ms 10844 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Incorrect 3 ms 10844 KB Output isn't correct
3 Halted 0 ms 0 KB -