oj.uz

Submission #929052

# Submission time Handle Problem Language Result Execution time Memory
929052 2024-02-17T15:06:45 Z NourWael Deda (COCI17_deda) C++17
20 / 140
 70 ms 17612 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std; 
int const mxN = 2e5+5;
int n,q, seg[8*mxN], a[8*mxN];
 
int get ( int node, int l_n, int r_n, int l, int r, int v) {
   if(seg[node]>v) return 1e17;
   if(l_n==r_n-1) return l_n;
   int m = (l_n+r_n)/2;
   if(seg[node*2+1]<=v && m>l && l_n<r) return get(node*2+1, l_n, m, l, r, v );
   else if(seg[node*2+2]<=v && (r>m && l<r_n)) return get(node*2+2, m, r_n, l, r, v );
   else return 1e17;
}
 
void update(int node, int l, int r, int x, int v ) {
   if(l==r-1) { seg[node] = v; return; }
   int m = (l+r)/2;
   if(x<m) update(node*2+1, l, m, x, v);
   else update(node*2+2, m, r, x, v);
   seg[node] = min(seg[node*2+1], seg[node*2+2]);
}
int dist[mxN];
 
signed main() {
  
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
 
  cin>>n>>q;
  int pw = (1<<(__lg(n)+1));
  for(int i=0; i<8*mxN; i++) seg[i] = 1e17;
  for(int i=0; i<=n; i++) dist[i] = 1e17;
 
  for(int i=0; i<q; i++) {
   char c; cin>>c;
   if(c=='M') {
       int x,a; cin>>x>>a;
       update(0,0,pw,a,x);
       dist[a] = x;
   }
   else  {
      int rides,b; cin>>rides>>b;
      int ans = get(0,0,pw,b,n+1, rides);
      cout<<(ans==1e17? -1:ans)<<'\n';
      bool f = 1;
      //for(int j=b; j<=n; j++) if(dist[j]<=rides) { cout<<j<<'\n'; f = 0; break;}
        // if(f) cout<<"-1\n";
   }
  }
  return 0;
}

Compilation message

deda.cpp: In function 'int main()':
deda.cpp:47:12: warning: unused variable 'f' [-Wunused-variable]
   47 |       bool f = 1;
      |            ^

Subtask #1
20.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 14424 KB Output is correct
2 Incorrect 3 ms 14428 KB Output isn't correct
3 Incorrect 4 ms 14428 KB Output isn't correct
4 Incorrect 53 ms 17612 KB Output isn't correct
5 Incorrect 63 ms 17236 KB Output isn't correct
6 Incorrect 70 ms 17400 KB Output isn't correct
7 Incorrect 69 ms 17460 KB Output isn't correct