oj.uz

Submission #471590

# Submission time Handle Problem Language Result Execution time Memory
471590 2021-09-10T02:03:37 Z Rainbowbunny Examination (JOI19_examination) C++17
100 / 100
 766 ms 48820 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;

int n, q;
int ans[MAXN];
vector <int> VX, VY;
vector <int> BIT2D[MAXN], V2D[MAXN];
vector <pair <int, pair <int, int> > > Student;
vector <pair <pair <int, int>, pair <int, int> > > Queries;
vector <pair <pair <int, int>, pair <int, int> > > QBIT;

void FakeAdd(int x, int y)
{
    for(x; x < MAXN; x += x & -x)
    {
        V2D[x].push_back(y);
    }
}

void FakeGet(int x, int y)
{
    for(x; x > 0; x -= x & -x)
    {
        V2D[x].push_back(y);
    }
}

void Add(int x, int y)
{
    for(x; x < MAXN; x += x & -x)
    {
        int tmp = lower_bound(V2D[x].begin(), V2D[x].end(), y) - V2D[x].begin() + 1;
        for(tmp; tmp < (int)BIT2D[x].size(); tmp += tmp & -tmp)
        {
            BIT2D[x][tmp]++;
        }
    }
}

int Get(int x, int y)
{
    int ans = 0;
    for(x; x > 0; x -= x & -x)
    {
        int tmp = lower_bound(V2D[x].begin(), V2D[x].end(), y) - V2D[x].begin() + 1;
        for(tmp; tmp > 0; tmp -= tmp & -tmp)
        {
            ans += BIT2D[x][tmp];
        }
    }
    return ans;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> q;
    for(int i = 1; i <= n; i++)
    {
        int x, y;
        cin >> x >> y;
        Student.emplace_back(x + y, make_pair(x, y));
        VX.push_back(x);
        VY.push_back(y);
    }
    for(int i = 1; i <= q; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        VX.push_back(x);
        VY.push_back(y);
        Queries.emplace_back(make_pair(z, i), make_pair(x, y));
    }
    sort(Student.begin(), Student.end());
    sort(Queries.begin(), Queries.end());
    sort(VX.begin(), VX.end());
    sort(VY.begin(), VY.end());
    VX.erase(unique(VX.begin(), VX.end()), VX.end());
    VY.erase(unique(VY.begin(), VY.end()), VY.end());
    while(Student.empty() == false and Queries.empty() == false)
    {
        if(Student.back().first >= Queries.back().first.first)
        {
            QBIT.emplace_back(make_pair(1, 0), Student.back().second);
            Student.pop_back();
        }
        else
        {
            QBIT.emplace_back(make_pair(2, Queries.back().first.second), Queries.back().second);
            Queries.pop_back();
        }
    }
    while(Queries.empty() == false)
    {
        QBIT.emplace_back(make_pair(2, Queries.back().first.second), Queries.back().second);
        Queries.pop_back();
    }
    for(auto &e : QBIT)
    {
        e.second.first = VX.end() - lower_bound(VX.begin(), VX.end(), e.second.first);
        e.second.second = VY.end() - lower_bound(VY.begin(), VY.end(), e.second.second);
        if(e.first.first == 1)
        {
            FakeAdd(e.second.first, e.second.second);
        }
        else
        {
            FakeGet(e.second.first, e.second.second);
        }
    }
    for(int i = 1; i < MAXN; i++)
    {
        sort(V2D[i].begin(), V2D[i].end());
        V2D[i].erase(unique(V2D[i].begin(), V2D[i].end()), V2D[i].end());
        BIT2D[i].resize((int)V2D[i].size() + 1);
    }
    for(auto e : QBIT)
    {
        if(e.first.first == 1)
        {
            Add(e.second.first, e.second.second);
        }
        else
        {
            ans[e.first.second] = Get(e.second.first, e.second.second);
        }
    }
    for(int i = 1; i <= q; i++)
    {
        cout << ans[i] << '\n';
    }
}

Compilation message

examination.cpp: In function 'void FakeAdd(int, int)':
examination.cpp:16:9: warning: statement has no effect [-Wunused-value]
   16 |     for(x; x < MAXN; x += x & -x)
      |         ^
examination.cpp: In function 'void FakeGet(int, int)':
examination.cpp:24:9: warning: statement has no effect [-Wunused-value]
   24 |     for(x; x > 0; x -= x & -x)
      |         ^
examination.cpp: In function 'void Add(int, int)':
examination.cpp:32:9: warning: statement has no effect [-Wunused-value]
   32 |     for(x; x < MAXN; x += x & -x)
      |         ^
examination.cpp:35:13: warning: statement has no effect [-Wunused-value]
   35 |         for(tmp; tmp < (int)BIT2D[x].size(); tmp += tmp & -tmp)
      |             ^~~
examination.cpp: In function 'int Get(int, int)':
examination.cpp:45:9: warning: statement has no effect [-Wunused-value]
   45 |     for(x; x > 0; x -= x & -x)
      |         ^
examination.cpp:48:13: warning: statement has no effect [-Wunused-value]
   48 |         for(tmp; tmp > 0; tmp -= tmp & -tmp)
      |             ^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15948 KB Output is correct
2 Correct 19 ms 15892 KB Output is correct
3 Correct 18 ms 15852 KB Output is correct
4 Correct 18 ms 15848 KB Output is correct
5 Correct 18 ms 15968 KB Output is correct
6 Correct 18 ms 15940 KB Output is correct
7 Correct 33 ms 16988 KB Output is correct
8 Correct 36 ms 16964 KB Output is correct
9 Correct 33 ms 16964 KB Output is correct
10 Correct 28 ms 16788 KB Output is correct
11 Correct 30 ms 16808 KB Output is correct
12 Correct 26 ms 16712 KB Output is correct
13 Correct 32 ms 16892 KB Output is correct
14 Correct 32 ms 16972 KB Output is correct
15 Correct 32 ms 16864 KB Output is correct
16 Correct 36 ms 16780 KB Output is correct
17 Correct 40 ms 16760 KB Output is correct
18 Correct 25 ms 16504 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 662 ms 44004 KB Output is correct
2 Correct 633 ms 44052 KB Output is correct
3 Correct 624 ms 44128 KB Output is correct
4 Correct 301 ms 38168 KB Output is correct
5 Correct 353 ms 39712 KB Output is correct
6 Correct 178 ms 34028 KB Output is correct
7 Correct 637 ms 43636 KB Output is correct
8 Correct 606 ms 43772 KB Output is correct
9 Correct 591 ms 42532 KB Output is correct
10 Correct 328 ms 38720 KB Output is correct
11 Correct 257 ms 37600 KB Output is correct
12 Correct 152 ms 32992 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 662 ms 44004 KB Output is correct
2 Correct 633 ms 44052 KB Output is correct
3 Correct 624 ms 44128 KB Output is correct
4 Correct 301 ms 38168 KB Output is correct
5 Correct 353 ms 39712 KB Output is correct
6 Correct 178 ms 34028 KB Output is correct
7 Correct 637 ms 43636 KB Output is correct
8 Correct 606 ms 43772 KB Output is correct
9 Correct 591 ms 42532 KB Output is correct
10 Correct 328 ms 38720 KB Output is correct
11 Correct 257 ms 37600 KB Output is correct
12 Correct 152 ms 32992 KB Output is correct
13 Correct 701 ms 44384 KB Output is correct
14 Correct 680 ms 44484 KB Output is correct
15 Correct 658 ms 44128 KB Output is correct
16 Correct 350 ms 38520 KB Output is correct
17 Correct 366 ms 40160 KB Output is correct
18 Correct 186 ms 34032 KB Output is correct
19 Correct 675 ms 44368 KB Output is correct
20 Correct 667 ms 44520 KB Output is correct
21 Correct 698 ms 43328 KB Output is correct
22 Correct 331 ms 38740 KB Output is correct
23 Correct 254 ms 37516 KB Output is correct
24 Correct 149 ms 32952 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 15948 KB Output is correct
2 Correct 19 ms 15892 KB Output is correct
3 Correct 18 ms 15852 KB Output is correct
4 Correct 18 ms 15848 KB Output is correct
5 Correct 18 ms 15968 KB Output is correct
6 Correct 18 ms 15940 KB Output is correct
7 Correct 33 ms 16988 KB Output is correct
8 Correct 36 ms 16964 KB Output is correct
9 Correct 33 ms 16964 KB Output is correct
10 Correct 28 ms 16788 KB Output is correct
11 Correct 30 ms 16808 KB Output is correct
12 Correct 26 ms 16712 KB Output is correct
13 Correct 32 ms 16892 KB Output is correct
14 Correct 32 ms 16972 KB Output is correct
15 Correct 32 ms 16864 KB Output is correct
16 Correct 36 ms 16780 KB Output is correct
17 Correct 40 ms 16760 KB Output is correct
18 Correct 25 ms 16504 KB Output is correct
19 Correct 662 ms 44004 KB Output is correct
20 Correct 633 ms 44052 KB Output is correct
21 Correct 624 ms 44128 KB Output is correct
22 Correct 301 ms 38168 KB Output is correct
23 Correct 353 ms 39712 KB Output is correct
24 Correct 178 ms 34028 KB Output is correct
25 Correct 637 ms 43636 KB Output is correct
26 Correct 606 ms 43772 KB Output is correct
27 Correct 591 ms 42532 KB Output is correct
28 Correct 328 ms 38720 KB Output is correct
29 Correct 257 ms 37600 KB Output is correct
30 Correct 152 ms 32992 KB Output is correct
31 Correct 701 ms 44384 KB Output is correct
32 Correct 680 ms 44484 KB Output is correct
33 Correct 658 ms 44128 KB Output is correct
34 Correct 350 ms 38520 KB Output is correct
35 Correct 366 ms 40160 KB Output is correct
36 Correct 186 ms 34032 KB Output is correct
37 Correct 675 ms 44368 KB Output is correct
38 Correct 667 ms 44520 KB Output is correct
39 Correct 698 ms 43328 KB Output is correct
40 Correct 331 ms 38740 KB Output is correct
41 Correct 254 ms 37516 KB Output is correct
42 Correct 149 ms 32952 KB Output is correct
43 Correct 755 ms 48524 KB Output is correct
44 Correct 734 ms 48820 KB Output is correct
45 Correct 766 ms 48520 KB Output is correct
46 Correct 375 ms 42036 KB Output is correct
47 Correct 376 ms 43804 KB Output is correct
48 Correct 185 ms 34012 KB Output is correct
49 Correct 727 ms 48352 KB Output is correct
50 Correct 725 ms 48720 KB Output is correct
51 Correct 725 ms 48304 KB Output is correct
52 Correct 322 ms 42980 KB Output is correct
53 Correct 302 ms 40636 KB Output is correct