oj.uz

Submission #839442

# Submission time Handle Problem Language Result Execution time Memory
839442 2023-08-30T03:17:06 Z Tuanlinh123 Examination (JOI19_examination) C++17
100 / 100
 1137 ms 89396 KB 
// #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

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.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 13 ms 2388 KB Output is correct
8 Correct 13 ms 2388 KB Output is correct
9 Correct 13 ms 2388 KB Output is correct
10 Correct 8 ms 2080 KB Output is correct
11 Correct 6 ms 980 KB Output is correct
12 Correct 3 ms 1104 KB Output is correct
13 Correct 12 ms 2392 KB Output is correct
14 Correct 13 ms 2388 KB Output is correct
15 Correct 13 ms 2388 KB Output is correct
16 Correct 3 ms 852 KB Output is correct
17 Correct 7 ms 2004 KB Output is correct
18 Correct 3 ms 852 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 858 ms 64692 KB Output is correct
2 Correct 807 ms 64700 KB Output is correct
3 Correct 840 ms 62916 KB Output is correct
4 Correct 331 ms 55876 KB Output is correct
5 Correct 212 ms 22324 KB Output is correct
6 Correct 87 ms 22148 KB Output is correct
7 Correct 637 ms 60044 KB Output is correct
8 Correct 730 ms 62264 KB Output is correct
9 Correct 600 ms 58936 KB Output is correct
10 Correct 115 ms 17084 KB Output is correct
11 Correct 261 ms 50864 KB Output is correct
12 Correct 63 ms 18820 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 858 ms 64692 KB Output is correct
2 Correct 807 ms 64700 KB Output is correct
3 Correct 840 ms 62916 KB Output is correct
4 Correct 331 ms 55876 KB Output is correct
5 Correct 212 ms 22324 KB Output is correct
6 Correct 87 ms 22148 KB Output is correct
7 Correct 637 ms 60044 KB Output is correct
8 Correct 730 ms 62264 KB Output is correct
9 Correct 600 ms 58936 KB Output is correct
10 Correct 115 ms 17084 KB Output is correct
11 Correct 261 ms 50864 KB Output is correct
12 Correct 63 ms 18820 KB Output is correct
13 Correct 942 ms 69196 KB Output is correct
14 Correct 931 ms 69428 KB Output is correct
15 Correct 822 ms 65400 KB Output is correct
16 Correct 352 ms 57808 KB Output is correct
17 Correct 220 ms 22948 KB Output is correct
18 Correct 95 ms 22296 KB Output is correct
19 Correct 835 ms 62584 KB Output is correct
20 Correct 860 ms 65332 KB Output is correct
21 Correct 840 ms 67272 KB Output is correct
22 Correct 116 ms 17136 KB Output is correct
23 Correct 263 ms 52540 KB Output is correct
24 Correct 61 ms 18872 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 13 ms 2388 KB Output is correct
8 Correct 13 ms 2388 KB Output is correct
9 Correct 13 ms 2388 KB Output is correct
10 Correct 8 ms 2080 KB Output is correct
11 Correct 6 ms 980 KB Output is correct
12 Correct 3 ms 1104 KB Output is correct
13 Correct 12 ms 2392 KB Output is correct
14 Correct 13 ms 2388 KB Output is correct
15 Correct 13 ms 2388 KB Output is correct
16 Correct 3 ms 852 KB Output is correct
17 Correct 7 ms 2004 KB Output is correct
18 Correct 3 ms 852 KB Output is correct
19 Correct 858 ms 64692 KB Output is correct
20 Correct 807 ms 64700 KB Output is correct
21 Correct 840 ms 62916 KB Output is correct
22 Correct 331 ms 55876 KB Output is correct
23 Correct 212 ms 22324 KB Output is correct
24 Correct 87 ms 22148 KB Output is correct
25 Correct 637 ms 60044 KB Output is correct
26 Correct 730 ms 62264 KB Output is correct
27 Correct 600 ms 58936 KB Output is correct
28 Correct 115 ms 17084 KB Output is correct
29 Correct 261 ms 50864 KB Output is correct
30 Correct 63 ms 18820 KB Output is correct
31 Correct 942 ms 69196 KB Output is correct
32 Correct 931 ms 69428 KB Output is correct
33 Correct 822 ms 65400 KB Output is correct
34 Correct 352 ms 57808 KB Output is correct
35 Correct 220 ms 22948 KB Output is correct
36 Correct 95 ms 22296 KB Output is correct
37 Correct 835 ms 62584 KB Output is correct
38 Correct 860 ms 65332 KB Output is correct
39 Correct 840 ms 67272 KB Output is correct
40 Correct 116 ms 17136 KB Output is correct
41 Correct 263 ms 52540 KB Output is correct
42 Correct 61 ms 18872 KB Output is correct
43 Correct 1076 ms 83400 KB Output is correct
44 Correct 1137 ms 85100 KB Output is correct
45 Correct 1104 ms 85592 KB Output is correct
46 Correct 437 ms 67260 KB Output is correct
47 Correct 245 ms 23100 KB Output is correct
48 Correct 96 ms 22304 KB Output is correct
49 Correct 1062 ms 86712 KB Output is correct
50 Correct 1094 ms 83452 KB Output is correct
51 Correct 1118 ms 89396 KB Output is correct
52 Correct 136 ms 17288 KB Output is correct
53 Correct 364 ms 64984 KB Output is correct