Submission #195560

#	Time	Username	Problem	Language	Result	Execution time	Memory
195560		theStaticMind	Examination (JOI19_examination)	C++14	100 / 100	2223 ms	14748 KiB

examination

#include<bits/stdc++.h>
#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;

struct Person{
      int M,I,Z,ind;
      bool Q;
      Person(int m,int i,int z,int in){
            M=m;
            I=i;
            Z=z;
            ind=in;
      }
      bool operator<(const Person& A)const{
            return M<A.M||(M==A.M&&I<A.I);
      }
};
vector<Person>arr;
vector<Person>Q;
vector<int>no;
vector<vector<ii>> data;
int sq;
int sz;
bool sort_by_Z(int A,int B){
      return arr[A].Z<arr[B].Z;
}
bool Sort_by_Z(int A,int B){
      return Q[A].Z<Q[B].Z;
}
int query(vector<ii>& data,int x){
      int l=0,r=data.size()-1;
      int j=data.size();
      while(l<=r){
            int mid=(l+r)/2;
            if(data[mid].first<x)l=mid+1;
            else{
                  r=mid-1;
                  j=mid;
            }
      }
      if(j==data.size())return 0;
      return data[j].second;
}
void erase(vector<ii>& data,int x){
      int l=0,r=data.size()-1;
      int j=data.size();
      while(l<=r){
            int mid=(l+r)/2;
            if(data[mid].first<x)l=mid+1;
            else{
                  r=mid-1;
                  j=mid;
            }
      }
      assert(j!=data.size());
      for(;j>=0;j--){
            data[j].second--;
      }
}
int32_t main(){
      ios_base::sync_with_stdio(false);
      cin.tie(NULL);
//      freopen("q.in","r",stdin);
//      freopen("q.out","w",stdout);
      int n,q;
      cin>>n>>q;
      vector<int>Z;
      vector<int>ans(q,0);
      for(int i=0;i<n;i++){
            int a,b;
            cin>>a>>b;
            arr.pb(Person(a,b,a+b,i));
            Z.pb(i);
      }
      sort(all(arr));
      for(int i=0;i<n;i++)arr[i].ind=i;
      sort(all(Z),sort_by_Z);

      sq=sqrt(n);
      sz=n/sq+1;
      for(int i=0;i<n;i++){
            no.pb(i/sq);
      }
      data.resize(sz);
      for(int i=0;i<n;i++){
            data[no[i]].pb({arr[i].I,0});
      }
      for(int i=0;i<sz;i++){
            int cnt=1;
            sort(all(data[i]));
            for(int j=data[i].size()-1;j>=0;j--){
                  data[i][j].second=cnt++;
            }
      }

      vector<int>idq;
      for(int i=0;i<q;i++){
            int a,b,c;
            cin>>a>>b>>c;
            idq.pb(i);
            Q.pb(Person(a,b,c,i));
      }
      sort(all(idq),Sort_by_Z);
      int ptr=0;
      vector<bool>vis(n,false);
      for(int i=0;i<q;i++){
            while(ptr!=n&&arr[Z[ptr]].Z<Q[idq[i]].Z){
                  vis[Z[ptr]]=true;
                  erase(data[no[arr[Z[ptr]].ind]],arr[Z[ptr]].I);
                  ptr++;
            }
            int l=0,r=n-1;
            int j=n;
            while(l<=r){
                  int mid=(l+r)/2;
                  if(arr[mid].M<Q[idq[i]].M)l=mid+1;
                  else{
                        r=mid-1;
                        j=mid;
                  }
            }
            if(j==n)continue;
            while(j!=0&&j<n&&no[j]==no[j-1]){
                  if(vis[j]==false&&arr[j].I>=Q[idq[i]].I)
                  ans[idq[i]]++;
                  j++;
            }
            if(j==n)continue;
            for(int N=no[j];N<sz;N++){
                  ans[idq[i]]+=query(data[N],Q[idq[i]].I);
            }
      }
      for(int i=0;i<q;i++)cout<<ans[i]<<"\n";
}

Compilation message (stderr)

examination.cpp: In function 'int query(std::vector<std::pair<int, int> >&, int)':
examination.cpp:47:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if(j==data.size())return 0;
          ~^~~~~~~~~~~~~
In file included from /usr/include/c++/7/cassert:44:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:33,
                 from examination.cpp:1:
examination.cpp: In function 'void erase(std::vector<std::pair<int, int> >&, int)':
examination.cpp:61:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       assert(j!=data.size());
              ~^~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57