Submission #471333

#	Time	Username	Problem	Language	Result	Execution time	Memory
471333		spike1236	Examination (JOI19_examination)	C++14	100 / 100	1771 ms	62484 KiB

examination

#include <iostream>
#include <map>
#include <unordered_map>
#include <vector>
#include <algorithm>
///#pragma GCC optimize("O3")
///#pragma GCC target("avx,avx2,fma")
using namespace std;
#define f first
#define s second

const int MAXN = 2e5 + 10;
pair <int, int> a[MAXN];
map <int, vector <vector <int> > > q;
vector <int> fw[MAXN], comp, comp2[MAXN];
int ans[MAXN];

int get_a(int v) {
    return lower_bound(comp.begin(), comp.end(), v) - comp.begin() + 1;
}

int get_b(int x, int y) {
    return lower_bound(comp2[x].begin(), comp2[x].end(), y) - comp2[x].begin() + 1;
}

void pre_upd(int x, int y) {
    for(int i = get_a(x); i <= comp.size(); i += i & -i) comp2[i].push_back(y);
}

void pre_get(int x, int y) {
    for(int i = get_a(x); i > 0; i -= i & -i) comp2[i].push_back(y);
}

void upd(int x, int y, int val) {
    for(int i = get_a(x); i <= comp.size(); i += i & -i)
        for(int j = get_b(i, y); j <= comp2[i].size(); j += j & -j)
            fw[i][j] += val;
}

int get(int x, int y) {
    int res = 0;
    for(int i = get_a(x); i > 0; i -= i & -i) {
        for(int j = get_b(i, y); j > 0; j -= j & -j) {
            res += fw[i][j];
        }
    }
    return res;
}

bool cmp(const pair <int, int> &x, const pair <int, int> &y) {
    return (x.f + x.s < y.f + y.s);
}

int main() {
    int n, qq;
    cin >> n >> qq;
    for(int i = 0; i < n; ++i) {
        cin >> a[i].f >> a[i].s;
        comp.push_back(a[i].f);
    }
    sort(a, a + n, &cmp);
    int x, y, z;
    for(int i = 0; i < qq; ++i) {
        cin >> x >> y >> z;
        q[z].push_back({x, y, i});
        comp.push_back(x - 1);
    }
    comp.push_back(1e9);
    sort(comp.begin(), comp.end());
    comp.erase(unique(comp.begin(), comp.end()), comp.end());
    for(int i = 0; i < n; ++i) pre_upd(a[i].f, a[i].s);
    for(auto &it : q) {
        for(auto &j : it.s) {
            pre_get(j[0] - 1, j[1] - 1);
            pre_get(j[0] - 1, 1e9);
            pre_get(1e9, j[1] - 1);
        }
    }
    for(int i = 1; i <= comp.size(); ++i) {
        sort(comp2[i].begin(), comp2[i].end());
        comp2[i].erase(unique(comp2[i].begin(), comp2[i].end()), comp2[i].end());
        fw[i].resize(comp2[i].size() + 1);
    }
    for(int i = 0; i < n; ++i) upd(a[i].f, a[i].s, 1);
    int ptr = 0;
    for(auto it : q) {
        while(ptr < n && a[ptr].f + a[ptr].s < it.f) {
            upd(a[ptr].f, a[ptr].s, -1);
            ++ptr;
        }
        for(auto j : q[it.f]) {
            ans[j[2]] = n - ptr - get(j[0] - 1, 1e9) - get(1e9, j[1] - 1) + get(j[0] - 1, j[1] - 1);
        }
    }
    for(int i = 0; i < qq; ++i) cout << ans[i] << '\n';
    return 0;
}

Compilation message (stderr)

examination.cpp: In function 'void pre_upd(int, int)':
examination.cpp:27:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i = get_a(x); i <= comp.size(); i += i & -i) comp2[i].push_back(y);
      |                           ~~^~~~~~~~~~~~~~
examination.cpp: In function 'void upd(int, int, int)':
examination.cpp:35:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i = get_a(x); i <= comp.size(); i += i & -i)
      |                           ~~^~~~~~~~~~~~~~
examination.cpp:36:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(int j = get_b(i, y); j <= comp2[i].size(); j += j & -j)
      |                                  ~~^~~~~~~~~~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:79:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i = 1; i <= comp.size(); ++i) {
      |                    ~~^~~~~~~~~~~~~~

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