Submission #996149

#	Time	Username	Problem	Language	Result	Execution time	Memory
996149		Neco_arc	Examination (JOI19_examination)	C++17	0 / 100	350 ms	74216 KiB

examination

#include <bits/stdc++.h>
//#include <bits/debug.hpp>

#define ll long long
#define all(x) x.begin(), x.end()
#define Neco "Examination"
#define resp(x) sort(all(x)), x.resize(unique(all(x)) - x.begin())
#define getbit(x,i) ((x >> i)&1)
#define _left id * 2, l, mid
#define _right id * 2 + 1, mid + 1, r
#define cntbit(x) __builtin_popcountll(x)
#define fi(i, a, b) for(int i = a; i <= b; i++)
#define fid(i, a, b) for(int i = a; i >= b; i--)
#define maxn (int) 6e5 + 7

using namespace std;

const ll mod = 1e9 + 7; //972663749
const ll base = 911382323;

int n, q;
vector<ll> Val;
int ans[maxn];
struct dl {
    ll x, y, z, id;
} qr[maxn];

struct BIT {
    vector<int> bit[maxn], nodes[maxn];

    void init(vector<pair<int, int>> P) {
        sort(all(P), [](pair<int, int> x, pair<int, int> y) { return x.second < y.second; });
        for(auto [x, y] : P) {
            for(int u = x; u < maxn; u += (u & -u)) {
                if(nodes[u].empty() || nodes[u].back() != y) nodes[u].push_back(y);
            }
        }

        fi(i, 1, maxn - 2) bit[i].resize(nodes[i].size() + 2);
    }

    int GetID(int x, int val) {
        return upper_bound(all(nodes[x]), val) - nodes[x].begin();
    }

    void update(int u, int v) {
        for(int x = u; x < maxn; x += (x & -x))
        for(int y = GetID(x, v); y < bit[x].size(); y += (y & -y)) {
            bit[x][y] ++;
        }
    }

    int get(int u, int v, int ans = 0) {
        for(int x = u; x > 0; x -= (x & -x))
        for(int y = GetID(x, v); y > 0; y -= (y & -y)) {
            ans += bit[x][y];
        }
        return ans;
    }

    int get(int x, int y, int u, int v) {
        return get(u, v) - get(u, y - 1) - get(x - 1, v) + get(x - 1, y - 1);
    }

} Bit;

void solve()
{

    cin >> n >> q;
    fi(i, 1, n + q) {
        if(i <= n) cin >> qr[i].x >> qr[i].y, qr[i].z = qr[i].x + qr[i].y;
        else cin >> qr[i].x >> qr[i].y >> qr[i].z;

        qr[i].id = (i > n) ? i - n : -i;
        Val.push_back(qr[i].x);
        Val.push_back(qr[i].y);
        Val.push_back(qr[i].z);
    }

    resp(Val);
    int N = Val.size();

    auto getv = [&](ll x) {
        return upper_bound(all(Val), x) - Val.begin();
    };

    vector<pair<int, int>> todo;

    fi(i, 1, n + q) {
        qr[i].x = getv(qr[i].x);
        qr[i].y = getv(qr[i].y);
        qr[i].z = getv(qr[i].z);

        if(i <= n) todo.push_back({qr[i].y, qr[i].z});
    }


    Bit.init(todo);
    sort(qr + 1, qr + 1 + n + q, [](dl x, dl y) { return x.x > y.x; } );

    fi(i, 1, n + q) {
        int x = qr[i].x, y = qr[i].y, z = qr[i].z, id = qr[i].id;

        if(id < 0) Bit.update(y, z);
        else ans[id] = Bit.get(y, z, N, N);
    }

    fi(i, 1, q) cout << ans[i] << '\n';

}


int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    if(fopen(Neco".inp", "r")) {
        freopen(Neco".inp", "r", stdin);
        freopen(Neco".out", "w", stdout);
    }


    int nTest = 1;
//    cin >> nTest;


    while(nTest--)
    {
        solve();
    }


    return 0;
}

Compilation message (stderr)

examination.cpp: In member function 'void BIT::update(int, int)':
examination.cpp:48:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for(int y = GetID(x, v); y < bit[x].size(); y += (y & -y)) {
      |                                  ~~^~~~~~~~~~~~~~~
examination.cpp: In function 'void solve()':
examination.cpp:103:13: warning: unused variable 'x' [-Wunused-variable]
  103 |         int x = qr[i].x, y = qr[i].y, z = qr[i].z, id = qr[i].id;
      |             ^
examination.cpp: In function 'int main()':
examination.cpp:122:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         freopen(Neco".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:123:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |         freopen(Neco".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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