oj.uz

Submission #142867

# Submission time Handle Problem Language Result Execution time Memory
142867 2019-08-11T17:17:07 Z Ort Deda (COCI17_deda) C++11
140 / 140
 407 ms 3664 KB 
#include<bits/stdc++.h>
#define MEM(a, b) memset(a, (b), sizeof(a))
#define ALL(c) (c).begin(),(c).end()
#define ll long long
#define LINF (ll)1e18
#define INF (int)1e9
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MAX 1<<18

using namespace std;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

int tree[2*MAX];

void update(int k, int x) {
	k+=MAX;
	tree[k]=x;
	for(k/=2;k>=1;k/=2) {
		tree[k]=min(tree[2*k],tree[2*k+1]);
	}
}

int query(int a, int b) {
    a+=MAX;b+=MAX;
    int p=INF;
    while(a<=b) {
        if(a%2==1) p=min(p,tree[a++]);
        if(b%2==0) p=min(p,tree[b--]);
        a/=2;b/=2;
    }
    return p;
}


int main() {
	IO;
	for(int i=0;i<2*MAX;i++) tree[i] = INF;
	int n, q; cin >> n >> q;
	while(q--) {
		char c; int a, b;
		cin >> c >> a >> b;
		if(c=='M') update(b, a);	
		else {
			int l = b; int h = MAX;
			while(l<h) {
				int mid = (l+h)>>1;
				int tr = query(l, mid);
				if(a>=tr) h = mid;
				else l = mid+1;
			}
			if(l>=MAX) cout << -1 << "\n";
			else cout << l << "\n";
		}
	}
	return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2424 KB Output is correct
2 Correct 4 ms 2428 KB Output is correct
3 Correct 10 ms 2424 KB Output is correct
4 Correct 407 ms 3664 KB Output is correct
5 Correct 309 ms 3360 KB Output is correct
6 Correct 333 ms 3320 KB Output is correct
7 Correct 370 ms 3508 KB Output is correct