Submission #127598

#	Time	Username	Problem	Language	Result	Execution time	Memory
127598		Mercenary	Examination (JOI19_examination)	C++14	100 / 100	894 ms	43372 KiB

examination

#include<bits/stdc++.h>

using namespace std;
#define taskname "A"
#define pb	push_back
#define mp 	make_pair
#ifndef LOCAL
#define cerr if(0)cout
#endif

typedef long double ld;
typedef long long ll;
typedef pair<int,int> ii;
const int N = 2e5 + 5;

int n , q;
vector<int> ID[N];
vector<int> BIT[N];

struct Node{
    int x , y , sum , id;
}a[N] , b[N];

void FakeUpdate(int x , int y){
    for( ; x > 0 ; x &= x - 1){
        ID[x].pb(y);
    }
}

void FakeQuery(int x , int y){
    for( ; x < N ; x += x & -x){
        ID[x].pb(y);
    }
}

int query(int x ,int yy){
    int res = 0;
    for( ; x < N ; x += x & -x){
        for(int y = lower_bound(ID[x].begin(),ID[x].end(),yy) - ID[x].begin() + 1
            ; y <= ID[x].size() ; y += y & -y){
            res += BIT[x][y - 1];
        }
    }
    return res;
}

void update(int x , int yy){
//    int res = 0;
    for( ; x > 0 ; x &= x - 1){
        for(int y = lower_bound(ID[x].begin(),ID[x].end(),yy) - ID[x].begin() + 1
            ; y > 0 ; y &= y - 1){
            ++BIT[x][y - 1];
        }
    }
//    return res;
}

void compress(){
    vector<int> X , Y , SUM;
    X.reserve(n + q);Y.reserve(n + q);SUM.reserve(n + q);
    for(int i = 1 ; i <= n ; ++i){
        X.pb(a[i].x);Y.pb(a[i].y);SUM.pb(a[i].x + a[i].y);
        a[i].sum = a[i].x + a[i].y;
    }
    for(int i = 1 ; i <= q ; ++i){
        X.pb(b[i].x);Y.pb(b[i].y);SUM.pb(b[i].sum);
    }
    sort(X.begin(),X.end());X.erase(unique(X.begin(),X.end()),X.end());
    sort(Y.begin(),Y.end());Y.erase(unique(Y.begin(),Y.end()),Y.end());
    sort(SUM.begin(),SUM.end());SUM.erase(unique(SUM.begin(),SUM.end()),SUM.end());
    for(int i = 1 ; i <= n ; ++i){
        a[i].x = lower_bound(X.begin(),X.end(),a[i].x) - X.begin() + 1;
        a[i].y = lower_bound(Y.begin(),Y.end(),a[i].y) - Y.begin() + 1;
        a[i].sum = lower_bound(SUM.begin(),SUM.end(),a[i].sum) - SUM.begin() + 1;
    }
    for(int i = 1 ; i <= q ; ++i){
        b[i].x = lower_bound(X.begin(),X.end(),b[i].x) - X.begin() + 1;
        b[i].y = lower_bound(Y.begin(),Y.end(),b[i].y) - Y.begin() + 1;
        b[i].sum = lower_bound(SUM.begin(),SUM.end(),b[i].sum) - SUM.begin() + 1;
    }
    for(int i = 1 ; i <= n ; ++i){
        FakeUpdate(a[i].x , a[i].y);
    }
    for(int i = 1 ; i <= q ; ++i){
        FakeQuery(b[i].x , b[i].y);
    }
    for(int i = 1 ; i < N ; ++i){
        sort(ID[i].begin(),ID[i].end());
        ID[i].erase(unique(ID[i].begin(),ID[i].end()),ID[i].end());
        BIT[i].resize(ID[i].size());
    }
}

int res[N];

void solve(){
    sort(b + 1 , b + q + 1 , [](const Node x , const Node y){
        return x.sum < y.sum;
         });
    sort(a + 1 , a + n + 1 , [](const Node x , const Node y){
        return x.sum < y.sum;
         });
    int j = n;
    for(int i = q ; i >= 1 ; --i){
        while(j >= 1 && a[j].sum >= b[i].sum){
            update(a[j].x,a[j].y);
//            cout << a[j].x << " " << a[j].y << endl;
            --j;
        }
//        cout << b[i].id << " " << b[i].x << " " << b[i].y << endl;
        res[b[i].id] = query(b[i].x , b[i].y);
    }
    for(int i = 1 ; i <= q ; ++i)cout << res[i] << '\n';
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    cin >> n >> q;
    for(int i = 1 ; i <= n ; ++i){
        cin >> a[i].x >> a[i].y;
    }
    for(int i = 1 ; i <= q ; ++i){
        cin >> b[i].x >> b[i].y >> b[i].sum;
        b[i].id = i;
    }
    compress();
    solve();
}

Compilation message (stderr)

examination.cpp: In function 'int query(int, int)':
examination.cpp:40:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             ; y <= ID[x].size() ; y += y & -y){
               ~~^~~~~~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:121:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".INP", "r",stdin);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:122:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   freopen(taskname".OUT", "w",stdout);
   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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