Submission #1110446

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1110446	2024-11-09T13:09:59 Z	_uros9	Deda (COCI17_deda)	C++17	140 / 140	131 ms	17368 KB

deda

#include <bits/stdc++.h>
#define endl '\n'
#define int long long

using namespace std;

const long long longlongmax=9223372036854775807;
const int modul=998244353;
const long long mod = 1e9 + 7;


mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());

const int N=200009,INF=100000000000009;
struct Cvor{
    Cvor(){}
    Cvor(int val,int l,int d){this->val=val;this->l=l;this->d=d;}
    int val,l,d;
};
Cvor seg[4*N];

void upd(int node,int l,int d,int ind,int value){
    if(l==d&&d==ind) {seg[node]=Cvor(value,l,d); return;}
    if(d<ind||l>ind) return;
    int s=l+d>>1;
    upd(2*node,l,s,ind,value);
    upd(2*node+1,s+1,d,ind,value);
    seg[node]=Cvor(min(seg[2*node].val,seg[2*node+1].val),l,d);
}
vector<int> bitni;
void query(int node,int l,int d,int poc,int kr){
    if(poc<=l&&d<=kr){bitni.push_back(node); return;}
    if(d<poc||l>kr) return;
    int s=l+d>>1;
    query(2*node,l,s,poc,kr);
    query(2*node+1,s+1,d,poc,kr);
}
int query2(int node,int l,int d,int Y){
    if(l==d) return l;
    int s=l+d>>1;
    if(seg[2*node].val<=Y)
        return query2(2*node,l,s,Y);
    return query2(2*node+1,s+1,d,Y);
}
int n,q;


signed main(){

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    //freopen("factory.in","r",stdin);
    //freopen("factory.out","w",stdout);



    cin >> n >> q;
    for(int i=1; i<=n; i++) upd(1,1,n,i,INF);
    while(q--){
        char c;
        cin >> c;
        if(c=='M'){
            int x,ind;
            cin >> x >> ind;
            upd(1,1,n,ind,x);
        }
        else{
            int Y,B;
            cin >> Y >> B;
            query(1,1,n,B,n);
            int rez=-1;
            for(auto x:bitni){
                if(seg[x].val<=Y){
                    rez=query2(x,seg[x].l,seg[x].d,Y);
                    break;
                }
            }
            cout << rez << endl;
            bitni.clear();
        }
    }

    return 0;
}
/*
    abcde
    01234
    04321 --> 12340
              0   1
    011
    110

1
3 1
1 2 3
3 5

*/

Compilation message

deda.cpp: In function 'void upd(long long int, long long int, long long int, long long int, long long int)':
deda.cpp:25:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |     int s=l+d>>1;
      |           ~^~
deda.cpp: In function 'void query(long long int, long long int, long long int, long long int, long long int)':
deda.cpp:34:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   34 |     int s=l+d>>1;
      |           ~^~
deda.cpp: In function 'long long int query2(long long int, long long int, long long int, long long int)':
deda.cpp:40:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   40 |     int s=l+d>>1;
      |           ~^~

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	2 ms	336 KB	Output is correct
3	Correct	2 ms	336 KB	Output is correct
4	Correct	116 ms	17368 KB	Output is correct
5	Correct	91 ms	10572 KB	Output is correct
6	Correct	108 ms	17168 KB	Output is correct
7	Correct	131 ms	17228 KB	Output is correct