oj.uz

Submission #219559

# Submission time Handle Problem Language Result Execution time Memory
219559 2020-04-05T14:56:57 Z shashwatchandra Simple game (IZhO17_game) C++17
100 / 100
 93 ms 11292 KB 
/*input
3 3
1 5 1
2 3
1 1 5
2 3
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define int long long 
#define double long double
#define f first
#define s second
#define mp make_pair
#define pb push_back

#define RE(i,n) for (int i = 1; i <= n; i++)
#define RED(i,n) for (int i = n; i > 0; i--)
#define REPS(i,n) for(int i = 1; (i*i) <= n; i++)
#define REP(i,n) for (int i = 0; i < (int)n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)

#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define print(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout << *it << " "; cout << endl;
#define debug(x) cout << x << endl;
#define debug2(x,y) cout << x << " " << y << endl;
#define debug3(x,y,z) cout << x << " " << y << " " << z << endl;

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

const int INF = 1e18+1;
const int MOD = 1e9+7;
const double PI = 3.14159265358979323846264338;

int raise(int a,int n,int m = MOD){
  if(n == 0)return 1;
  if(n == 1)return a;
  int x = 1;
    x *= raise(a,n/2,m);
    x %= m;
    x *= x;
    x %= m;
    if(n%2)x*= a;
    x %= m;
    return x;
}

int floor1(int n,int k){
    if(n%k == 0 || n >= 0)return n/k;
    return (n/k)-1;
}

int ceil1(int n,int k){
    return floor1(n+k-1,k);
}

const int N = 1e6+1;
int bit[N];
int n,q;
int a[N];

void upd(int ind,int x){
	while(ind < N){
		bit[ind] += x;
		ind += ind&(-ind);
	}
}

int suma(int ind){
	int res = 0;
	while(ind){
		res += bit[ind];
		ind -= ind&(-ind);
	}
	return res;
}

void solve(){
  	cin >> n >> q;
  	RE(i,n){
  		cin >> a[i];
  	}
  	RE(ind,n){
  		/*if(ind > 1){
  			upd(max(a[ind-1],a[ind]),-1);
  			upd(min(a[ind-1],a[ind]),1);
  		}*/
  		if(ind < n){
  			upd(min(a[ind+1],a[ind]),1);
  			upd(max(a[ind+1],a[ind]),-1);
  		}
  	}
  	while(q--){
  		int ty;cin >> ty;
  		if(ty == 1){
  			int ind,nw;cin >> ind >> nw;
  			if(ind > 1){
  				upd(min(a[ind-1],a[ind]),-1);
  				upd(max(a[ind-1],a[ind]),1);
  			}
  			if(ind < n){
  				upd(min(a[ind+1],a[ind]),-1);
  				upd(max(a[ind+1],a[ind]),1);
  			}
  			a[ind] = nw;
  			if(ind > 1){
  				upd(min(a[ind-1],a[ind]),1);
  				upd(max(a[ind-1],a[ind]),-1);
  			}
  			if(ind < n){
  				upd(min(a[ind+1],a[ind]),1);
  				upd(max(a[ind+1],a[ind]),-1);
  			}
  		}
  		else{
  			int hx;cin >> hx;
  			cout << suma(hx) << "\n";
  		}

  	}
}

signed main(){
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  //freopen(".in","r",stdin);freopen(".out","w",stdout);
  int t = 1;
  //cin >> t;
  while(t--){
    solve();
  }
  return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 9 ms 6016 KB Output is correct
3 Correct 8 ms 5888 KB Output is correct
4 Correct 8 ms 6144 KB Output is correct
5 Correct 8 ms 6016 KB Output is correct
6 Correct 9 ms 6144 KB Output is correct
7 Correct 6 ms 512 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 9 ms 6016 KB Output is correct
3 Correct 8 ms 5888 KB Output is correct
4 Correct 8 ms 6144 KB Output is correct
5 Correct 8 ms 6016 KB Output is correct
6 Correct 9 ms 6144 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 43 ms 2172 KB Output is correct
9 Correct 64 ms 11212 KB Output is correct
10 Correct 64 ms 11128 KB Output is correct
11 Correct 46 ms 2168 KB Output is correct
12 Correct 54 ms 3448 KB Output is correct
13 Correct 49 ms 3192 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 9 ms 6016 KB Output is correct
3 Correct 8 ms 5888 KB Output is correct
4 Correct 8 ms 6144 KB Output is correct
5 Correct 8 ms 6016 KB Output is correct
6 Correct 9 ms 6144 KB Output is correct
7 Correct 6 ms 512 KB Output is correct
8 Correct 43 ms 2172 KB Output is correct
9 Correct 64 ms 11212 KB Output is correct
10 Correct 64 ms 11128 KB Output is correct
11 Correct 46 ms 2168 KB Output is correct
12 Correct 54 ms 3448 KB Output is correct
13 Correct 49 ms 3192 KB Output is correct
14 Correct 93 ms 11240 KB Output is correct
15 Correct 93 ms 11292 KB Output is correct
16 Correct 84 ms 11000 KB Output is correct
17 Correct 84 ms 11128 KB Output is correct
18 Correct 85 ms 11128 KB Output is correct