답안 #881320

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
881320 2023-12-01T06:38:12 Z _unknown_2010 Simple game (IZhO17_game) C++17
0 / 100
5 ms 16732 KB
//#ifndef LOCAL
//#pragma GCC optimize ("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#endif

#include <bits/stdc++.h>
using namespace std;
using vecp = vector<pair<int,int>>;
#define vecm(a,n,m) vector<vector<int>>a(n,vector<int>(m,0));
#define int int64_t
#define pb  push_back
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define mpii map<int,int>
#define lb lower_bound
#define ub upper_bound
#define foor(i,a,b) for(int i=a;i<b; i++)
#define foor(i,a) foor(i,0,a)
#define ins insert
#define ss second
#define ff first
#define until(x, a) for (auto x : a)
#define ln(x) int(x.size())
#define all(x) (x).begin(), (x).end()
#define seea(a,n) for(int i=0;i<n;i++){cin>>a[i];}
#define seev(v,n) for(int i=0;i<n;i++){int x; cin>>x; v.push_back(x);}
const int mod = 1E9+7;
struct segtree{
    vi tree;
    int sz;
    void init(int n){
        sz=1;
        while(sz<n)sz*=2;
        tree.assign(2*sz-1,0);
    }
    void update(int i,int v,int x,int lx,int rx){
        if(rx-lx==1){
            tree[x]+=v;
            return;
        }
        int m=(lx+rx)/2;
        if(i<m)update(i,v,2*x+1,lx,m);
        else update(i,v,2*x+2,m,rx);
        tree[x]=tree[2*x+1]+tree[2*x+2];
    }
    void update(int i,int v){
        return update(i,v,0,0,sz);
    }
    int sum(int l,int r,int x,int lx,int rx){
        if(rx<=l || r<=lx)return 0;
        if(l<=lx && rx<=r)return tree[x];
        int m=(lx+rx)/2;
        int s1=sum(l,r,2*x+1,lx,m);
        int s2=sum(l,r,2*x+2,m,rx);
        return s1+s2;
    }
    int sum(int l,int r){
        return sum(l,r,0,0,sz);
    }
};
void solution(){
    int n,m;
    cin >> n >> m;
    int a[n];
    segtree st;
    int maks=0;
    for(int i=0; i<n; i++){
        cin >> a[i];
        maks=max(a[i],maks);
    }
    st.init(maks);
    for(int i=1; i<n; i++){
        int mn=min(a[i],a[i-1]);
        int mx=max(a[i],a[i-1]);
        st.update(mn-1,1);
        if(mx!=maks)
            st.update(maks,-1);
    }
    while(m--){
        int op;
        cin >> op;
        if(op==2){
            int k;
            cin >> k;
            if(k>maks)cout << 0;
            else cout << st.sum(0,k) << endl;
        }
        else {
            int i,v;
            cin >> i >> v;
            if(i==1){
                int mn=min(a[i],a[i-1]);
                int mx=max(a[i],a[i-1]);
                st.update(mn-1,-1);
                if(mx!=maks)
                    st.update(mx,1);
                a[i-1]=v;
                mn=min(a[i],a[i-1]);
                mx=max(a[i],a[i-1]);
                st.update(mn-1,1);
                if(mx!=maks)
                    st.update(mx,-1);
            }
            else if(i==n){
                int mn=min(a[i-2],a[i-1]);
                int mx=max(a[i-2],a[i-1]);
                st.update(mn-1,-1);
                if(mx!=maks)
                    st.update(mx,1);
                a[i-1]=v;
                mn=min(a[i-1],a[i-2]);
                mx=max(a[i-1],a[i-2]);
                st.update(mn-1,1);
                if(mx!=maks)
                    st.update(mx,-1);
           }
           else {
                i--;
                int mn=min(a[i],a[i-1]);
                int mx=max(a[i],a[i-1]);
                st.update(mn-1,-1);
                if(mx!=maks)
                    st.update(mx,1);
                mn=min(a[i-1],a[i-2]);
                mx=max(a[i-1],a[i-2]);
                st.update(mn-1,-1);
                if(mx!=maks)
                    st.update(mx,1);
                a[i]=v;
                mn=min(a[i],a[i-1]);
                mx=max(a[i],a[i-1]);
                st.update(mn-1,1);
                if(mx!=maks)
                    st.update(mx,-1);
                mn=min(a[i-2],a[i-1]);
                mx=max(a[i-2],a[i-1]);
                st.update(mn-1,1);
                if(mx!=maks)
                    st.update(mx,1);
           }
           }
    }
}
int32_t main(){
    clock_t tStart = clock();
    std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int q = 1; // cin >> q;
    while(q--) {
        solution();
        cout << '\n';
    }
    cerr<<fixed<<setprecision(3)<<"\nTime Taken: "<<(double)(clock()- tStart)/CLOCKS_PER_SEC<<endl;
}
/*

██╗  ██╗ █████╗  ██████╗     ██╗██╗   ██╗ ██████╗████████╗
██║░░██║██╔══██╗██╔════╝░░░░░██║██║░░░██║██╔════╝╚══██╔══╝
███████║██║░░██║╚█████╗░░░░░░██║██║░░░██║╚█████╗░░░░██║░░░
██╔══██║██║░░██║░╚═══██╗██╗░░██║██║░░░██║░╚═══██╗░░░██║░░░
██║░░██║╚█████╔╝██████╔╝╚█████╔╝╚██████╔╝██████╔╝░░░██║░░░
╚═╝░░╚═╝░╚════╝░╚═════╝░░╚════╝░░╚═════╝░╚═════╝░░░░╚═╝░░░
*/

Compilation message

game.cpp:19: warning: "foor" redefined
   19 | #define foor(i,a) foor(i,0,a)
      | 
game.cpp:18: note: this is the location of the previous definition
   18 | #define foor(i,a,b) for(int i=a;i<b; i++)
      |
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 5 ms 16732 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 5 ms 16732 KB Output isn't correct
3 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Incorrect 5 ms 16732 KB Output isn't correct
3 Halted 0 ms 0 KB -