Submission #82461

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
82461	2018-10-30T19:51:09 Z	Genezio	Deda (COCI17_deda)	C++14	140 / 140	195 ms	3804 KB

deda

#include<bits/stdc++.h>

using namespace std;
#define pii pair<int,int>
#define mp make_pair
#define F first
#define S second
#define pb push_back
#define ll long long
#define fe 2*x+1
#define fd 2*x+2
#define m ((l+r)>>1)

const int N = 200010;
const int INF = 0x3f3f3f3f;
const ll mod = 1e9+7;

 int v[N];
 int tree[4*N];

 void build(int x,int l,int r) {
 	if(l==r) {
 		tree[x]=INF;
 		return;
 	}
 	build(fe,l,m);
 	build(fd,m+1,r);
 	tree[x]=min(tree[fe],tree[fd]);
 }

 void upd(int x,int l,int r,int p,int v) {
 	if(l==r) {
 		tree[x]=v;
 		return;
 	}
 	if(p<=m) {
 		upd(fe,l,m,p,v);
 	} else {
 		upd(fd,m+1,r,p,v);
 	}
 	tree[x]=min(tree[fe],tree[fd]);
 }

 int query(int x,int l,int r,int ql,int qr,int v) {
 	if(r<ql||l>qr) {
 		return INF;
 	}
 	if(l==r) {
 		if(tree[x]<=v) return l;
 		else return INF;
 	}
 	if(ql<=l&&r<=qr) {
 		if(tree[fe]<=v) return query(fe,l,m,ql,qr,v);
 		else if(tree[fd]<=v) return query(fd,m+1,r,ql,qr,v);
 		else return INF;
 	}
 	return min(query(fe,l,m,ql,qr,v),query(fd,m+1,r,ql,qr,v));
 }


int main() {
	ios::sync_with_stdio(false);
 	cin.tie(0);
    int n,q,a,b;
    char c;
    cin>>n>>q;
    build(0,0,n-1);
    for(int i=0;i<q;i++) {
        cin>>c>>a>>b;
        if(c=='M') {
        	upd(0,0,n-1,b-1,a);
        } else {
        	int aux=query(0,0,n-1,b-1,n-1,a);
        	if(aux==INF) cout<<"-1\n";
        	else cout<<aux+1<<"\n"; 
        }
    }
    /*for(int i=0;i<4*n;i++) {
    	cout<<i<<" "<<tree[i]<<"\n";
    }*/
    return 0;
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	380 KB	Output is correct
2	Correct	2 ms	476 KB	Output is correct
3	Correct	4 ms	544 KB	Output is correct
4	Correct	166 ms	3804 KB	Output is correct
5	Correct	154 ms	3804 KB	Output is correct
6	Correct	184 ms	3804 KB	Output is correct
7	Correct	195 ms	3804 KB	Output is correct