Submission #839442

#	Time	Username	Problem	Language	Result	Execution time	Memory
839442		Tuanlinh123	Examination (JOI19_examination)	C++17	100 / 100	1137 ms	89396 KiB

examination

// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define ll long long
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
using namespace std;

struct BIT
{
    ll n;
    vector<vector<ll>> node, bit;

    BIT(ll n) : n(n)
    {
        node.resize(n + 5);
        bit.resize(n + 5);
    }

    void addNode_Update(ll x, ll y)
    {
        for (x; x <= n; x += x & (-x))
            node[x].pb(y);
    }

    void addNode_Query(ll x, ll y)
    {
        for (x; x > 0; x -= x & (-x))
            node[x].pb(y);
    }

    void init()
    {
        for (ll i=0; i<node.size(); i++)
        {
            sort(node[i].begin(), node[i].end());
            node[i].resize(unique(node[i].begin(), node[i].end())-node[i].begin());
            bit[i].assign(node[i].size(), 0);
        }
    }

    void addNode_range(ll x1, ll y1, ll x2, ll y2)
    {
        addNode_Query(x2, y2);
        addNode_Query(x1 - 1, y2);
        addNode_Query(x2, y1 - 1);
        addNode_Query(x1 - 1, y1 - 1);
    }

    void update(ll x, ll yy, ll val)
    {
        // cout << x << " " << yy << " " << val << " u\n";
        for (x; x <= n; x += x & (-x))
            for (ll y = lower_bound(node[x].begin(), node[x].end(), yy) - node[x].begin() + 1; y <= node[x].size(); y += y & (-y))
                bit[x][y - 1] += val;
    }

    ll query(ll x, ll yy)
    {
        ll ans = 0; 
        // cout << x << " " << yy << " ";
        for (x; x > 0; x -= x & (-x))
            for (ll y = lower_bound(node[x].begin(), node[x].end(), yy) - node[x].begin() + 1; y > 0; y -= y & (-y))
                assert(y<=node[x].size()), ans += bit[x][y - 1];
        // cout << ans << " q\n";
        return ans;
    }

    ll range(ll x1, ll y1, ll x2, ll y2)
    {
        return query(x2, y2) - query(x1 - 1, y2) - query(x2, y1 - 1) + query(x1 - 1, y1 - 1);
    }
};

pll a[200005];
vector<ll> nen;
ll ans[200005];
vector<pair<pll, pll>> Q;

bool cmp(pll a, pll b)
{
    return a.fi + a.se > b.fi + b.se;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);    
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    ll n, q;
    cin >> n >> q;
    for (ll i = 1; i <= n; i++)
    {
        cin >> a[i].fi >> a[i].se;
        nen.pb(a[i].fi);
    }
    sort(a + 1, a + n + 1, cmp);
    for (ll i = 1; i <= q; i++)
    {
        ll a, b, c;
        cin >> a >> b >> c;
        Q.pb({{c, i}, {a, b}});
        nen.pb(a);
    }
    sort(nen.begin(), nen.end());
    nen.resize(unique(nen.begin(), nen.end()) - nen.begin());
    ll k = nen.size();
    BIT A(k);
    for (ll i = 1; i <= n; i++)
        A.addNode_Update(lower_bound(nen.begin(), nen.end(), a[i].fi) - nen.begin() + 1, a[i].se);
    sort(Q.begin(), Q.end(), greater<pair<pll, pll>>());
    for (ll i = 0; i < q; i++)
        A.addNode_range(lower_bound(nen.begin(), nen.end(), Q[i].se.fi) - nen.begin() + 1, Q[i].se.se, k, 2e9);
    A.init();
    ll ptr = 1;
    for (ll i = 0; i < q; i++)
    {
        ll c = Q[i].fi.fi, idx = Q[i].fi.se, aa = Q[i].se.fi, bb = Q[i].se.se;
        while (ptr <= n && a[ptr].fi + a[ptr].se >= c)
            A.update(lower_bound(nen.begin(), nen.end(), a[ptr].fi) - nen.begin() + 1, a[ptr].se, 1), ptr++;
        ans[idx] = A.range(lower_bound(nen.begin(), nen.end(), aa) - nen.begin() + 1, bb, k, 2e9);
        //cout << aa << " " << bb << " " << c << endl;
    }
    // cout << "bruh" << endl;
    for (ll i = 1; i <= q; i++)
        cout << ans[i] << "\n";
}

Compilation message (stderr)

examination.cpp: In member function 'void BIT::addNode_Update(long long int, long long int)':
examination.cpp:25:14: warning: statement has no effect [-Wunused-value]
   25 |         for (x; x <= n; x += x & (-x))
      |              ^
examination.cpp: In member function 'void BIT::addNode_Query(long long int, long long int)':
examination.cpp:31:14: warning: statement has no effect [-Wunused-value]
   31 |         for (x; x > 0; x -= x & (-x))
      |              ^
examination.cpp: In member function 'void BIT::init()':
examination.cpp:37:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for (ll i=0; i<node.size(); i++)
      |                      ~^~~~~~~~~~~~
examination.cpp: In member function 'void BIT::update(long long int, long long int, long long int)':
examination.cpp:56:14: warning: statement has no effect [-Wunused-value]
   56 |         for (x; x <= n; x += x & (-x))
      |              ^
examination.cpp:57:98: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |             for (ll y = lower_bound(node[x].begin(), node[x].end(), yy) - node[x].begin() + 1; y <= node[x].size(); y += y & (-y))
      |                                                                                                ~~^~~~~~~~~~~~~~~~~
examination.cpp: In member function 'long long int BIT::query(long long int, long long int)':
examination.cpp:65:14: warning: statement has no effect [-Wunused-value]
   65 |         for (x; x > 0; x -= x & (-x))
      |              ^
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from examination.cpp:2:
examination.cpp:67:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |                 assert(y<=node[x].size()), ans += bit[x][y - 1];
      |                        ~^~~~~~~~~~~~~~~~

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