Submission #142866

#	Time	Username	Problem	Language	Result	Execution time	Memory
142866		Ort	Deda (COCI17_deda)	C++11	60 / 140	399 ms	3504 KiB

deda

#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: 60 / 140