oj.uz

Submission #670578

# Submission time Handle Problem Language Result Execution time Memory
670578 2022-12-09T14:58:37 Z bojackduy Examination (JOI19_examination) C++14
2 / 100
 3000 ms 53012 KB 
#include <iostream>
#include <queue>
#include <stack>
#include <algorithm>
#include <string.h>
#include <functional>
#include <assert.h>
#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;
const int B = 5000;


int n, m, sz, numB;

#define get_id(x) (x + B - 1) / B
#define lef(x) (x - 1) * B + 1
#define rig(x) min(x * B, sz)

int idex[N];
array<int, 3> a[N];
int block[N / B + 1][N], ans[N];
vi store[N], bit[N];
void quick_sort(int l, int r) {
    int i = l, j = r, x = a[l + r >> 1][2];
    while (i <= j) {
        while (a[i][2] > x) i++;
        while (a[j][2] < x) j--;
        if (i <= j) {
            swap(a[i], a[j]);
            swap(idex[i], idex[j]);
            i++, j--;
        }
    }
    if (l < j) quick_sort(l, j);
    if (i < r) quick_sort(i, r);
}

void upd(int id, int x) {
    for (; x > 0 ; x -= x & -x) block[id][x]++;
}
int get(int id, int x) {
    int sum = 0;
    for (; x <= sz; x += x & -x) sum += block[id][x];
return sum;
}

void upd1(int id, int x) {
    for (; x > 0; x -= x & -x) bit[id][x]++;
}
int get1(int id, int x) {
    int sum = 0;
    for (; x < bit[id].size(); x += x & -x) sum += bit[id][x];
return sum;
}

void adj(int i) {
    int id = get_id(a[i][0]);
    upd(id, a[i][1]);
    int z = lower_bound(all(store[a[i][0]]), a[i][1]) - store[a[i][0]].begin() + 1;
    upd1(a[i][0], z);
}
int query(int i) {
    int res = 0;
    int id = get_id(a[i][0]);
    if (lef(id) != a[i][0]) id++;
    for (int j = id; j <= numB; j++) {
        res += get(j, a[i][1]);
    }
    if (lef(get_id(a[i][0])) != a[i][0]) {
        id = get_id(a[i][0]);
        for (int j = a[i][0]; j <= rig(id); j++) {
            int z = lower_bound(all(store[j]), a[i][1]) - store[j].begin() + 1;
            res += get1(j, z);
        }
    }
return res;
}

void solve(int test = -1) {
    cin >> n >> m;
    vector<array<int, 3>> b;
    for (int i = 1; i <= n; i++) {
        cin >> a[i][0] >> a[i][1];
        a[i][2] = a[i][0] + a[i][1];
        b.pb({a[i][0], i, 0});
        b.pb({a[i][1], i, 1});
        b.pb({a[i][2], i, 2});
    }
    for (int i = 1; i <= m; i++) {
        cin >> a[i + n][0] >> a[i + n][1] >> a[i + n][2];
        idex[i + n] = i;
        b.pb({a[i + n][0], i + n, 0});
        b.pb({a[i + n][1], i + n, 1});
        b.pb({a[i + n][2], i + n, 2});
    }
    sort(all(b));
    for (int i = 0; i < b.size(); i++) {
        if (i == 0 || b[i][0] != b[i - 1][0]) sz++;
        a[b[i][1]][b[i][2]] = sz;
    }
    numB = get_id(sz);

    for (int i = 1; i <= n; i++) {
        store[a[i][0]].pb(a[i][1]);
    }
    for (int i = 1; i <= sz; i++) {
        sort(all(store[i]));
        bit[i].resize(store[i].size() + 1);
    }

    sort(a + 1, a + 1 + n, [&](const array<int, 3> &x, const array<int, 3> &y) {
        return x[2] > y[2];
    });
    quick_sort(n + 1, n + m);
    int j = 1;
    for (int i = 1; i <= m; i++) {
        while (j <= n && a[j][2] >= a[i + n][2]) {
            adj(j);
            j++;
        }
        ans[idex[i + n]] = query(i + n);
    }
    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

examination.cpp: In function 'void quick_sort(int, int)':
examination.cpp:57:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |     int i = l, j = r, x = a[l + r >> 1][2];
      |                             ~~^~~
examination.cpp: In function 'int get1(int, int)':
examination.cpp:85:14: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
   85 |     for (; x < bit[id].size(); x += x & -x) sum += bit[id][x];
      |              ^
examination.cpp: In function 'void solve(int)':
examination.cpp:130:23: warning: comparison of integer expressions of different signedness: 'int' and 'long long unsigned int' [-Wsign-compare]
  130 |     for (int i = 0; i < b.size(); i++) {
      |                       ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28500 KB Output is correct
2 Correct 15 ms 28396 KB Output is correct
3 Correct 15 ms 28500 KB Output is correct
4 Correct 15 ms 28500 KB Output is correct
5 Correct 16 ms 28484 KB Output is correct
6 Correct 14 ms 28492 KB Output is correct
7 Correct 70 ms 29768 KB Output is correct
8 Correct 62 ms 29640 KB Output is correct
9 Correct 63 ms 29672 KB Output is correct
10 Correct 65 ms 29280 KB Output is correct
11 Correct 58 ms 29268 KB Output is correct
12 Correct 20 ms 29076 KB Output is correct
13 Correct 64 ms 29536 KB Output is correct
14 Correct 64 ms 29536 KB Output is correct
15 Correct 64 ms 29444 KB Output is correct
16 Correct 41 ms 29076 KB Output is correct
17 Correct 63 ms 29188 KB Output is correct
18 Correct 19 ms 29076 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3063 ms 53012 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3063 ms 53012 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 28500 KB Output is correct
2 Correct 15 ms 28396 KB Output is correct
3 Correct 15 ms 28500 KB Output is correct
4 Correct 15 ms 28500 KB Output is correct
5 Correct 16 ms 28484 KB Output is correct
6 Correct 14 ms 28492 KB Output is correct
7 Correct 70 ms 29768 KB Output is correct
8 Correct 62 ms 29640 KB Output is correct
9 Correct 63 ms 29672 KB Output is correct
10 Correct 65 ms 29280 KB Output is correct
11 Correct 58 ms 29268 KB Output is correct
12 Correct 20 ms 29076 KB Output is correct
13 Correct 64 ms 29536 KB Output is correct
14 Correct 64 ms 29536 KB Output is correct
15 Correct 64 ms 29444 KB Output is correct
16 Correct 41 ms 29076 KB Output is correct
17 Correct 63 ms 29188 KB Output is correct
18 Correct 19 ms 29076 KB Output is correct
19 Execution timed out 3063 ms 53012 KB Time limit exceeded
20 Halted 0 ms 0 KB -