Submission #557825

#	Time	Username	Problem	Language	Result	Execution time	Memory
557825		hibiki	Examination (JOI19_examination)	C++11	0 / 100	394 ms	21216 KiB

examination

#include<bits/stdc++.h>
using namespace std;

#define PB push_back
#define F first
#define S second

class FenwickTree
{
private:
    int N;
    vector<int> arr;
    map<int,int> compact;
public:
    FenwickTree() {}
    FenwickTree(int n,vector<int> v): N(n+5), arr(N,0)
    {
        for(int i=0;i<v.size();i++)
            compact[v[i]]=i;
    }

    void update(int idx,int val)
    {
        idx = compact[idx];

        idx++;
        while(idx<N)
        {
            arr[idx] += val;
            idx += idx & -idx;
        }
        return ;
    }

    int query(int idx)
    {
        idx = compact[idx] - 1;

        idx++;
        int ret=0;
        while(idx>0)
        {
            ret += arr[idx];
            idx -= idx & -idx;
        }
        return ret;
    }
};

int n,q;
int sA[100005],sB[100005];
int qA[100005],qB[100005],qC[100005],ans[100005];
map<int,int> ma,mb;
vector<int> va,vb;
vector<pair<int,pair<int,int> > > poi;

int main()
{
    scanf("%d %d",&n,&q);
    for(int i=0;i<n;i++)
    {
        scanf("%d %d",&sA[i],&sB[i]);
        poi.PB({ -(sA[i]+sB[i]) , {0,i} });
        if(!ma[sA[i]])
        {
            ma[sA[i]]=1;
            va.PB(sA[i]);
        }
        if(!mb[sB[i]])
        {
            mb[sB[i]]=1;
            vb.PB(sB[i]);
        }
    }
    for(int i=0;i<q;i++)
    {
        scanf("%d %d %d",&qA[i],&qB[i],&qC[i]);
        poi.PB({ -(max(qA[i]+qB[i],qC[i])) , {1,i} });
    }

    sort(poi.begin(),poi.end());
    sort(va.begin(),va.end());
    sort(vb.begin(),vb.end());

    int all=0;
    FenwickTree FwA(va.size(),va),FwB(vb.size(),vb);
    for(int i=0;i<poi.size();i++)
    {
        int ty=poi[i].S.F;
        int idx=poi[i].S.S;
        if(!ty)
        {
            all++;
            FwA.update(sA[idx],1);
            FwB.update(sB[idx],1);
        }
        else
        {
            int upA = *(lower_bound(va.begin(),va.end(),qA[idx]));
            int upB = *(lower_bound(vb.begin(),vb.end(),qB[idx]));
            ans[idx] = all - FwA.query(max(0,upA)) - FwB.query(max(0,upB));
        }
    }

    for(int i=0;i<q;i++)
        printf("%d\n",ans[i]);

    return 0;
}

Compilation message (stderr)

examination.cpp: In constructor 'FenwickTree::FenwickTree(int, std::vector<int>)':
examination.cpp:18:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         for(int i=0;i<v.size();i++)
      |                     ~^~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:87:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   87 |     for(int i=0;i<poi.size();i++)
      |                 ~^~~~~~~~~~~
examination.cpp:59:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |     scanf("%d %d",&n,&q);
      |     ~~~~~^~~~~~~~~~~~~~~
examination.cpp:62:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |         scanf("%d %d",&sA[i],&sB[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         scanf("%d %d %d",&qA[i],&qB[i],&qC[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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