Submission #606679

#	Time	Username	Problem	Language	Result	Execution time	Memory
606679		alireza_kaviani	Examination (JOI19_examination)	C++17	100 / 100	250 ms	16060 KiB

examination

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

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

#define all(x)      (x).begin(),(x).end()
#define X           first
#define Y           second
#define sep         ' '
#define endl        '\n'
#define SZ(x)       ll(x.size())

const ll MAXN = 1e5 + 10;
const ll LOG = 22;
const ll INF = 8e18;
const ll MOD = 1e9 + 7; //998244353; //1e9 + 9;

int n , q , A[MAXN] , B[MAXN] , C[MAXN] , ans[MAXN] , fen[2][MAXN];
vector<pii> sortA , sortB , sortC;
vector<pair<int , pii>> Q[MAXN];

void add(int ind , int x , int val){
    for(x++; x < MAXN ; x += x & -x)    fen[ind][x] += val;
}

int get(int ind , int x){
    int ans = 0;
    for(; x ; x -= x & -x)  ans += fen[ind][x];
    return ans;
}

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

    cin >> n >> q;
    for(int i = 0 ; i < n ; i++){
        cin >> A[i] >> B[i];
        C[i] = A[i] + B[i];
        sortA.push_back({A[i] , i});
        sortB.push_back({B[i] , i});
        sortC.push_back({C[i] , i});
    }
    sort(all(sortA));
    sort(all(sortB));
    sort(all(sortC));
    for(int i = 0 ; i < n ; i++){
        A[i] = lower_bound(all(sortA) , pii(A[i] , -MOD)) - sortA.begin();
        B[i] = lower_bound(all(sortB) , pii(B[i] , -MOD)) - sortB.begin();
        C[i] = lower_bound(all(sortC) , pii(C[i] , -MOD)) - sortC.begin();
    }

    for(int i = 0 ; i < q ; i++){
        int x , y , z;
        cin >> x >> y >> z;
        z = max(z , x + y);
        int indx = lower_bound(all(sortA) , pii(x , -MOD)) - sortA.begin();
        int indy = lower_bound(all(sortB) , pii(y , -MOD)) - sortB.begin();
        int indz = lower_bound(all(sortC) , pii(z , -MOD)) - sortC.begin();
        ans[i] = n - indx - indy - indz;
        Q[indz].push_back({i , {0 , indx}});
        Q[indz].push_back({i , {1 , indy}});
    }

    for(int i = 0 ; i <= n ; i++){
        for(pair<int , pii> j : Q[i]){
            ans[j.X] += get(j.Y.X , j.Y.Y);
        }
        add(0 , A[sortC[i].Y] , 1);
        add(1 , B[sortC[i].Y] , 1);
    }

    for(int i = 0 ; i < q ; i++){
        cout << ans[i] << endl;
    }

    return 0;
}
/*

*/

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