oj.uz

Submission #165197

# Submission time Handle Problem Language Result Execution time Memory
165197 2019-11-25T19:10:21 Z theStaticMind Deda (COCI17_deda) C++14
140 / 140
 170 ms 4740 KB 
#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;

int32_t main(){
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
   //   freopen("q.gir","r",stdin);
   //   freopen("q.cik","w",stdout);
      int n,q;
      cin>>n>>q;
      int sq=sqrt(n);
      vector<int>no;
      for(int i=0;i<=n;i++)no.pb(i/sq);
      vector<int>Mo(no.back()+1,INF);
      vector<int>P(n+1,INF);
      for(int i=0;i<q;i++){
            char c;
            int x,y;
            cin>>c>>x>>y;
            if(c=='M'){
                  P[y]=x;
                  Mo[no[y]]=min(Mo[no[y]],x);
            }
            else{
                  int ind=y,ans=-1;
                  while(ind<=n&&no[ind]==no[ind-1]){
                        if(P[ind]<=x){
                              ans=ind;
                              break;
                        }
                        ind++;
                  }
                  if(ind<=n&&ans==-1){
                        int N=no[ind];
                        while(N<Mo.size()&&Mo[N]>x)N++;
                        if(N!=Mo.size()){
                              ind=N*sq;
                              while(ind<=n&&no[ind]==N){
                                    if(P[ind]<=x){
                                          ans=ind;
                                          break;
                                    }
                                    ind++;
                              }
                        }
                  }
                  cout<<ans<<"\n";
            }
      }
}

Compilation message

deda.cpp: In function 'int32_t main()':
deda.cpp:43:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         while(N<Mo.size()&&Mo[N]>x)N++;
                               ~^~~~~~~~~~
deda.cpp:44:29: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                         if(N!=Mo.size()){
                            ~^~~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 170 ms 4740 KB Output is correct
5 Correct 96 ms 2796 KB Output is correct
6 Correct 121 ms 3856 KB Output is correct
7 Correct 126 ms 4576 KB Output is correct