Submission #839416

#	Time	Username	Problem	Language	Result	Execution time	Memory
839416		vjudge1	Examination (JOI19_examination)	C++17	100 / 100	351 ms	32836 KiB

examination

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

const int maxn = 2e5 + 5;
const int INF = 2e9 + 5;

int n, q;

pair<int, int> A[maxn];

pair<int, int> cp[maxn];

vector<int> FW[maxn], fake[maxn];
vector<int> qq[maxn];

pair<int, int> pos[maxn];
int ans[maxn];

void fadd(int x, int y) {
    for(x; x <= n; x += x&(-x)){
        fake[x].push_back(y);
    }
}

void add(int x, int y){
    for(x; x <= n; x += x&(-x)){
        for(int idx = upper_bound(fake[x].begin(), fake[x].end(), y) - fake[x].begin() - 1; idx < fake[x].size(); idx += idx&(-idx)) {
            FW[x][idx]++;
        }
    }
}

int query(int x, int y){
    int re = 0;
    for(x; x > 0; x -= x&(-x)) {
        for(int idx = upper_bound(fake[x].begin(), fake[x].end(), y) - fake[x].begin() - 1; idx > 0; idx -= idx&(-idx)) {
            re += FW[x][idx];
        }
    }
    return re;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> A[i].first >> A[i].second;
        A[i].first *= -1;
        A[i].second *= -1;
    }
    sort(A + 1, A + n + 1);
    for(int i = 1; i <= n; i++){
        cp[i] = {A[i].second, i};
    }
    sort(cp + 1, cp + n + 1);
    for (int i = 1; i <= q; i++)
    {
        int x, y, c;
        cin >> x >> y >> c;
        x *= -1;
        y *= -1;
        c *= -1;
        qq[upper_bound(A + 1, A + n + 1, make_pair(x, n)) - A-1].push_back(i);
        pos[i] = {upper_bound(cp+1, cp+n+1, make_pair(y, n)) - cp - 1, c};
    }
    for(int i = 1; i <= n; i++){
        // cout << cp[i].first << endl;
        A[cp[i].second] = {i, A[cp[i].second].first + A[cp[i].second].second};
    }
    for(int i = 1; i <= n; i++){
        fadd(A[i].first, A[i].second);
    }
    for(int i = 1; i <= n; i++){
        fake[i].push_back(-INF);
        sort(fake[i].begin(), fake[i].end());
        fake[i].erase(unique(fake[i].begin(), fake[i].end()), fake[i].end());
        FW[i].assign(fake[i].size(), 0);
    }
    for(int i = 1; i <= n; i++){
        add(A[i].first, A[i].second);
        for(auto v: qq[i]){
            ans[v] = query(pos[v].first, pos[v].second);
        }
    }
    for(int i = 1; i <= q; i++)cout << ans[i] << "\n";
}

Compilation message (stderr)

examination.cpp: In function 'void fadd(int, int)':
examination.cpp:20:9: warning: statement has no effect [-Wunused-value]
   20 |     for(x; x <= n; x += x&(-x)){
      |         ^
examination.cpp: In function 'void add(int, int)':
examination.cpp:26:9: warning: statement has no effect [-Wunused-value]
   26 |     for(x; x <= n; x += x&(-x)){
      |         ^
examination.cpp:27:97: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         for(int idx = upper_bound(fake[x].begin(), fake[x].end(), y) - fake[x].begin() - 1; idx < fake[x].size(); idx += idx&(-idx)) {
      |                                                                                             ~~~~^~~~~~~~~~~~~~~~
examination.cpp: In function 'int query(int, int)':
examination.cpp:35:9: warning: statement has no effect [-Wunused-value]
   35 |     for(x; x > 0; x -= x&(-x)) {
      |         ^

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