Submission #157285

#	Time	Username	Problem	Language	Result	Execution time	Memory
157285		combi1k1	Examination (JOI19_examination)	C++14	100 / 100	553 ms	26116 KiB

examination

#include<bits/stdc++.h>

using namespace std;

#define X       first
#define Y       second
#define pb      push_back
#define sz(x)   x.size()
#define all(x)  x.begin(),x.end()

const int   N   = 1e5 + 10;

namespace BIT2D {
    vector<int> val[N];
    vector<int> bit[N];

    void init() {
        for(int i = 1 ; i < N ; ++i)    {
            sort(all(val[i]));
            val[i].resize(unique(all(val[i])) - val[i].begin());
            bit[i].resize(sz(val[i]) + 5);
        }
    }
    int upd(int x,int y)    {
        for(; x > 0 ; x -= x & -x)  {
            int p = upper_bound(all(val[x]),y) - val[x].begin();
            for(; p > 0 ; p -= p & -p)
                bit[x][p]++;
        }
    }
    int get(int x,int y)    {
        int ans = 0;
        for(; x < N ; x += x & -x)  {
            int p = lower_bound(all(val[x]),y) - val[x].begin() + 1;
            for(; p <  bit[x].size() ; p += p & -p)
                ans += bit[x][p];
        }
        return  ans;
    }
};

typedef pair<int,int>   ii;

vector<ii>  Poi;
vector<int> Que;

int Math[N];
int Info[N];
int Sum[N];
int ans[N];

int main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;  cin >> n;   Poi.resize(n);
    int q;  cin >> q;

    vector<int> row = {-1};
    vector<int> col = {-1};

    for(ii &p : Poi)    {
        cin >> p.X >> p.Y;
        row.pb(p.X);
        col.pb(p.Y);
    }
    sort(all(Poi),[&](const ii &a,const ii &b)  {
         return  a.X + a.Y > b.X + b.Y;
    });

    sort(all(row)); row.erase(unique(all(row)),row.end());
    sort(all(col)); col.erase(unique(all(col)),col.end());

    for(ii &p : Poi)    {
        p.X = lower_bound(all(row),p.X) - row.begin();
        p.Y = lower_bound(all(col),p.Y) - col.begin();
        for(int i = p.X ; i > 0 ; i -= i & -i)
            BIT2D::val[i].push_back(p.Y);
    }

    for(int i = 0 ; i < q ; ++i)    {
        int M;  cin >> M;   Math[i] = lower_bound(all(row),M) - row.begin();
        int I;  cin >> I;   Info[i] = lower_bound(all(col),I) - col.begin();
        cin >> Sum[i];
        Que.pb(i);
    }

    sort(all(Que),[&](const int &a,const int &b)    {
         return  Sum[a] > Sum[b];
    });

    BIT2D::init();
    int ptr = 0;

    for(int i : Que)    {
        for(; ptr < Poi.size() ; ++ptr) {
            int x = Poi[ptr].X;
            int y = Poi[ptr].Y;
            if (row[x] + col[y] < Sum[i])
                break;
            BIT2D::upd(x,y);
        }
        ans[i] = BIT2D::get(Math[i],Info[i]);
    }

    for(int i = 0 ; i < q ; ++i)
        cout << ans[i] << "\n";
}

Compilation message (stderr)

examination.cpp: In function 'int BIT2D::upd(int, int)':
examination.cpp:30:5: warning: no return statement in function returning non-void [-Wreturn-type]
     }
     ^
examination.cpp: In function 'int BIT2D::get(int, int)':
examination.cpp:35:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(; p <  bit[x].size() ; p += p & -p)
                   ~~^~~~~~~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:96:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(; ptr < Poi.size() ; ++ptr) {
               ~~~~^~~~~~~~~~~~

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