# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
885530 | Requiem | Deda (COCI17_deda) | C++17 | 83 ms | 11096 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define INF 1e18
#define fi first
#define se second
#define endl "\n"
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define pi 3.14159265359
#define TASKNAME ""
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
int n,m;
const int MAXN = 2e5 + 9;
int st[MAXN<<2];
void update(int node,int l,int r,int pos,int val){
if (l==r){
st[node] = val;
return;
}
int mid = (l+r)>>1;
if (pos <= mid) update(node<<1,l,mid,pos,val);
else update(node<<1|1,mid+1,r,pos,val);
st[node] = min(st[node<<1], st[node<<1|1]);
}
int get(int node,int l,int r,int u,int v,int y){
int mid = (l+r)>>1;
if (l>=u and r<=v){
if (st[node] > y) return -1;
if (l==r) return l;
else if (st[node<<1] <= y) {
return get(node<<1,l,mid,u,v,y);
}
else if (st[node<<1|1] <= y){
return get(node<<1|1,mid+1,r,u,v,y);
}
else return -1;
}
if (l>v or r<u) return -1;
int g1 = get(node<<1,l,mid,u,v,y);
if (g1 != -1) return g1;
else return get(node<<1|1,mid+1,r,u,v,y);
}
main()
{
fast;
if (fopen(TASKNAME".inp","r")){
freopen(TASKNAME".inp","r",stdin);
freopen(TASKNAME".out","w",stdout);
}
cin>>n>>m;
memset(st,0x3f,sizeof(st));
for(int i=1;i<=m;i++){
char c;
int x,a;
cin>>c>>x>>a;
if (c == 'M'){
update(1,1,n,a,x);
}
else{
cout<<get(1,1,n,a,n,x)<<endl;
}
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |