Submission #670600

#	Time	Username	Problem	Language	Result	Execution time	Memory
670600		bojackduy	Examination (JOI19_examination)	C++14	100 / 100	828 ms	66372 KiB

examination

#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>
#include <string.h>
#include <functional>
#include <numeric>
#define task "task"
#define size() size() * 1ll 
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define fi first
#define se second
#define MASK(x) (1LL << (x))
#define BIT(x,i) (((x) >> (i)) & 1)
#define numbit(x) __builtin_popcountll(x)

using namespace std;

typedef vector<int> vi;
typedef vector<pii> vii;
typedef long long ll;

template<class t>
bool mini(t &x,t y) {
    if (y < x) {
       x = y;
       return 1;
    }
return 0;
}
template<class t>
bool maxi(t &x,t y) {
    if (x < y) {
       x = y;
       return 1;
    }
return 0;
}

const int N = 6e5 + 10;



int n, m, sz;


array<int, 3> a[N];
int ans[N];
vi store[N], v;
vector<vi> bit;

void adj(int x, int y) {
    x = lower_bound(all(v), x) - v.begin() + 1;
    for (;x > 0; x -= x & -x) {
        int i = lower_bound(all(store[x]), y) - store[x].begin() + 1;
        for (; i > 0; i -= i & -i) bit[x][i]++;
    }
}
int get(int x, int y) {
    int sum = 0;
    x = lower_bound(all(v), x) - v.begin() + 1;
    for (; x <= v.size(); x += x & -x) {
        int i = lower_bound(all(store[x]), y) - store[x].begin() + 1;
        for (; i <= store[x].size(); i += i & -i) sum += bit[x][i];
    }
return sum;
}
void solve(int test = -1) {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i][0] >> a[i][1];
        a[i][2] = a[i][0] + a[i][1];
    }
    for (int i = 1; i <= m; i++) {
        cin >> a[i + n][0] >> a[i + n][1] >> a[i + n][2];
    }

    vi id(m);
    iota(all(id), 1);
    sort(a + 1, a + 1 + n, [&](const array<int, 3> &x, const array<int, 3> &y) {
        return x[2] > y[2];
    });
    sort(all(id), [&](const int &x, const int &y) {
        return a[x + n][2] > a[y + n][2];
    });

    for (int i = 1; i <= n + m; i++)
        v.pb(a[i][0]);
    sort(all(v));
    v.erase(unique(all(v)), v.end());
    bit.resize(v.size() + 2, vi(0));

    for (int i = 1; i <= n + m; i++) {
        int z = lower_bound(all(v), a[i][0]) - v.begin() + 1;
        for (int j = z; j <= v.size(); j += j & -j) store[j].pb(a[i][1]);
        for (int j = z; j > 0; j -= j & -j) store[j].pb(a[i][1]);
    }    
    for (int i = 1; i <= v.size(); i++) {
        sort(all(store[i]));
        store[i].erase(unique(all(store[i])), store[i].end());
        bit[i].resize(store[i].size() + 2);
    }


    int j = 1;
    for (int i: id) {
        while (j <= n && a[j][2] >= a[i + n][2]) {
            adj(a[j][0], a[j][1]);
            j++;
        }
        ans[i] = get(a[i + n][0], a[i + n][1]);
    }
    for (int i = 1; i <= m; i++) cout << ans[i] << '\n';
}
int32_t main()  {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    // freopen(task".inp", "r", stdin);
    // freopen(task".out", "w", stdout);

    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; i++) {
        solve(i);
    }
return 0;
}
/*

*/

Compilation message (stderr)

examination.cpp: In function 'int get(int, int)':
examination.cpp:64:14: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   64 |     for (; x <= v.size(); x += x & -x) {
      |              ^
examination.cpp:66:18: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   66 |         for (; i <= store[x].size(); i += i & -i) sum += bit[x][i];
      |                  ^
examination.cpp: In function 'void solve(int)':
examination.cpp:97:27: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   97 |         for (int j = z; j <= v.size(); j += j & -j) store[j].pb(a[i][1]);
      |                           ^
examination.cpp:100:23: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
  100 |     for (int i = 1; i <= v.size(); i++) {
      |                       ^

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