oj.uz

Submission #137131

# Submission time Handle Problem Language Result Execution time Memory
137131 2019-07-27T06:20:41 Z KLPP Poklon (COCI17_poklon) C++14
140 / 140
 1975 ms 15116 KB 
#include<bits/stdc++.h>

using namespace std;
typedef long long int lld;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define block 700
int n,q;
int arr[1000000];
multiset<int> m;
struct queries{
  int l,r;
  int index;
};
bool operator <(queries a, queries b){
  if(a.l/block<b.l/block)return true;
  if(a.l/block>b.l/block)return false;
  return (a.r<b.r);
}
queries Q[1000000];
int L,R;
int freq[1000000];
int ans;
void Rplus(){
  R++;
  ans-=(freq[arr[R]]==2);
  freq[arr[R]]++;
  ans+=(freq[arr[R]]==2);
}
void Lminus(){
  L--;
  ans-=(freq[arr[L]]==2);
  freq[arr[L]]++;
  ans+=(freq[arr[L]]==2); 
}
void Rminus(){
  R--;
  ans-=(freq[arr[R+1]]==2);
  freq[arr[R+1]]--;
  ans+=(freq[arr[R+1]]==2);
}
void Lplus(){
  L++;
  ans-=(freq[arr[L-1]]==2);
  freq[arr[L-1]]--;
  ans+=(freq[arr[L-1]]==2); 
}
void adjust(int l, int r){
  while(R<r){
    Rplus();
  }
  while(l<L){
    Lminus();
  }
  while(r<R){
    Rminus();
  }
  while(L<l){
    Lplus();
  }
  //cout<<l<<" "<<r<<" "<<L<<" "<<R<<endl;
}
int main(){
  
  scanf("%d %d",&n,&q);
  vector<int> compress;
  rep(i,0,n){
    scanf("%d",&arr[i]);
    compress.push_back(arr[i]);
  }
  sort(compress.begin(),compress.end());
  rep(i,0,n){
    int lo,hi;
    lo=-1;
    hi=n;
    while(hi-lo>1){
      int mid=(hi+lo)/2;
      if(arr[i]>=compress[mid])lo=mid;
      else hi=mid;
    }
    arr[i]=lo;
    //cout<<arr[i]<<" ";
  }//cout<<endl;
  rep(i,0,n)freq[i]=0;
  ans=0;
  rep(i,0,q){
    scanf("%d %d",&Q[i].l,&Q[i].r);
    Q[i].l--;
    Q[i].r--;
    Q[i].index=i;
  }
  sort(Q,Q+q);
  int answer[n];
  L=0;
  R=-1;
  rep(i,0,q){
    adjust(Q[i].l,Q[i].r);
    /*cout<<L<<" "<<R<<endl;
    rep(i,0,n)cout<<freq[i]<<" ";
    cout<<endl;*/
    answer[Q[i].index]=ans;
  }
  rep(i,0,q){
    printf("%d\n",answer[i]);
  }
  return 0;
}

Compilation message

poklon.cpp: In function 'int main()':
poklon.cpp:64:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&n,&q);
   ~~~~~^~~~~~~~~~~~~~~
poklon.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&arr[i]);
     ~~~~~^~~~~~~~~~~~~~
poklon.cpp:86:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&Q[i].l,&Q[i].r);
     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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 3 ms 376 KB Output is correct
4 Correct 9 ms 508 KB Output is correct
5 Correct 185 ms 3416 KB Output is correct
6 Correct 199 ms 3384 KB Output is correct
7 Correct 495 ms 6380 KB Output is correct
8 Correct 919 ms 9256 KB Output is correct
9 Correct 1391 ms 12256 KB Output is correct
10 Correct 1975 ms 15116 KB Output is correct