oj.uz

Submission #441175

# Submission time Handle Problem Language Result Execution time Memory
441175 2021-07-04T13:18:30 Z leaked Simple game (IZhO17_game) C++14
100 / 100
 77 ms 6912 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//    #pragma GCC optimize("-O3")
//    #pragma GCC optimize("no-stack-protector")
//    #pragma GCC optimize("fast-math")
//    #pragma GCC optimize("Ofast")
//    #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//    #pragma GCC target("avx,avx2,fma")
//    #pragma GCC optimization ("unroll-loops")
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifndef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
//using namespace __gnu_pbds;
#define fast_io ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define vec vector
#define getin freopen("input.txt","r",stdin);
#define getout ofstream cout("output.txt");
#define getfiles getin;getout
#define m_p make_pair
#define f first
#define sz(x) (int)x.size()
#define pw(x) (1LL<<x)
#define pb push_back
#define endl '\n'
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define s second
typedef pair<int,int> pii;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
typedef long double ld;
template<typename T>bool umax(T &a,const T &b)  {return (a<b?a=b,1:0);}
template<typename T>bool umin(T &a,const T &b)  {return (a>b?a=b,1:0);}
const int N=1e6+3;
int fnw[N];
void add(int v,int x){
    v++;
    while(v<N){
        fnw[v]+=x;
        v+=v&-v;
    }
}
int get(int v){
    v++;
    int ans=0;
    while(v>0){
        ans+=fnw[v];
        v-=v&-v;
    }
    return ans;
}
signed main(){
//    ifstream cin("game.in");
//    ofstream cout("game.out");
    fast_io;
    int n,q;
    cin>>n>>q;
    vec<int>a(n);
    for(auto &z : a)
        cin>>z;
    for(int i=0;i+1<n;i++){
        int l=min(a[i],a[i+1]),r=max(a[i],a[i+1]);
        add(l,1);
        add(r+1,-1);
    }
    while(q--){
        int tp;
        cin>>tp;
        if(tp==1){
            int i,vl;
            cin>>i>>vl;--i;
            if(i){
                int l=min(a[i],a[i-1]),r=max(a[i],a[i-1]);
                add(l,-1);
                add(r+1,1);
            }
            if(i+1<n){
                int l=min(a[i],a[i+1]),r=max(a[i],a[i+1]);
                add(l,-1);
                add(r+1,1);
            }
            a[i]=vl;
            if(i){
                int l=min(a[i],a[i-1]),r=max(a[i],a[i-1]);
                add(l,1);
                add(r+1,-1);
            }
            if(i+1<n){
                int l=min(a[i],a[i+1]),r=max(a[i],a[i+1]);
                add(l,1);
                add(r+1,-1);
            }
        }
        else{
            int h;
            cin>>h;
            cout<<get(h)<<endl;
        }
    }
    return 0;
}
/*


*/

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 3 ms 4044 KB Output is correct
3 Correct 3 ms 4052 KB Output is correct
4 Correct 3 ms 4044 KB Output is correct
5 Correct 3 ms 4044 KB Output is correct
6 Correct 3 ms 4044 KB Output is correct
7 Correct 1 ms 332 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 3 ms 4044 KB Output is correct
3 Correct 3 ms 4052 KB Output is correct
4 Correct 3 ms 4044 KB Output is correct
5 Correct 3 ms 4044 KB Output is correct
6 Correct 3 ms 4044 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 41 ms 1732 KB Output is correct
9 Correct 54 ms 6728 KB Output is correct
10 Correct 51 ms 6832 KB Output is correct
11 Correct 43 ms 1652 KB Output is correct
12 Correct 47 ms 2768 KB Output is correct
13 Correct 45 ms 2800 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 3 ms 4044 KB Output is correct
3 Correct 3 ms 4052 KB Output is correct
4 Correct 3 ms 4044 KB Output is correct
5 Correct 3 ms 4044 KB Output is correct
6 Correct 3 ms 4044 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 41 ms 1732 KB Output is correct
9 Correct 54 ms 6728 KB Output is correct
10 Correct 51 ms 6832 KB Output is correct
11 Correct 43 ms 1652 KB Output is correct
12 Correct 47 ms 2768 KB Output is correct
13 Correct 45 ms 2800 KB Output is correct
14 Correct 73 ms 6784 KB Output is correct
15 Correct 77 ms 6724 KB Output is correct
16 Correct 72 ms 6912 KB Output is correct
17 Correct 75 ms 6720 KB Output is correct
18 Correct 76 ms 6816 KB Output is correct