oj.uz

Submission #137127

# Submission time Handle Problem Language Result Execution time Memory
137127 2019-07-27T06:06:00 Z KLPP Poklon (COCI17_poklon) C++14
0 / 140
 1972 ms 23780 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]]==2);
  freq[arr[R]]--;
  ans+=(freq[arr[R]]==2);
}
void Lplus(){
  L++;
  ans-=(freq[arr[L]]==2);
  freq[arr[L]]--;
  ans+=(freq[arr[L]]==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;
  }
  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:85: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
0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Incorrect 3 ms 376 KB Output isn't correct
4 Incorrect 9 ms 632 KB Output isn't correct
5 Incorrect 192 ms 4848 KB Output isn't correct
6 Incorrect 195 ms 4848 KB Output isn't correct
7 Incorrect 500 ms 9680 KB Output isn't correct
8 Incorrect 927 ms 14408 KB Output isn't correct
9 Incorrect 1397 ms 19060 KB Output isn't correct
10 Incorrect 1972 ms 23780 KB Output isn't correct