Submission #1096982

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096982		LonlyR	Examination (JOI19_examination)	C++17	100 / 100	541 ms	70796 KiB

examination

#include<bits/stdc++.h>
#define int long long
#define ii pair<int,int>
#define all(x) x.begin(), x.end()

using namespace std;
const int maxn = 6e5 + 4;
int n, m, q;
int ans[maxn];
vector<int> f[maxn], fake[maxn];
array<int, 4> qr[maxn], a[maxn];
vector<int> nen;

int comp(int x)
{
    return upper_bound(all(nen), x) - nen.begin();
}

void fupd(int x, int y)
{
    for (; x > 0; x -= x & -x)
        fake[x].emplace_back(y);
}

void fqry(int x, int y)
{
    for (; x <= nen.size(); x += x & -x)
        fake[x].emplace_back(y);
}

void build()
{
    for (int i = 1; i <= nen.size(); i++)
    {
        if (fake[i].empty()) continue;
        sort(all(fake[i]));
        fake[i].resize(unique(all(fake[i])) - fake[i].begin());
        f[i].resize(fake[i].size() + 1, 0);
    }
}

void upd(int x, int y)
{
    for (; x > 0; x -= x & -x)
        for (int i = lower_bound(all(fake[x]), y) - fake[x].begin() + 1; i > 0; i -= i & -i)
            f[x][i]++;
}

int qry(int x, int y)
{
    int ans = 0;
    for (; x <= nen.size(); x += x & -x)
        for (int i = lower_bound(all(fake[x]), y) - fake[x].begin() + 1; i <= fake[x].size(); i += i & -i)
            ans += f[x][i];
    return ans;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i][0] >> a[i][1], a[i][2] = a[i][0] + a[i][1];
        for (int j = 0; j < 3; j++)
            nen.emplace_back(a[i][0]),
            nen.emplace_back(a[i][1]),
            nen.emplace_back(a[i][2]);
    }
    for (int i = 1; i <= q; i++)
    {
        cin >> qr[i][0] >> qr[i][1] >> qr[i][2];
        qr[i][3] = i;
        for (int j = 0; j < 3; j++)
            nen.emplace_back(qr[i][j]);
    }
    sort(all(nen));
    nen.resize(unique(all(nen)) - nen.begin());

    sort(all(nen));
    nen.resize(unique(all(nen)) - nen.begin());
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j < 3; j++)
            a[i][j] = comp(a[i][j]);
        fupd(a[i][1], a[i][2]);
    }
    for (int i = 1; i <= q; i++)
    {
        auto &[u1, u2, v1, v2] = qr[i];
        u1 = comp(u1);
        u2 = comp(u2);
        v1 = comp(v1);
//        fqry(u2, v1);
    }
    build();
    sort(a + 1, a + n + 1, greater<>());
    sort(qr + 1, qr + q + 1, greater<>());
    for (int i = 1, j = 1; i <= q; i++)
    {
        while (j <= n && a[j][0] >= qr[i][0])
            upd(a[j][1], a[j][2]),
            j++;
        ans[qr[i][3]] = qry(qr[i][1], qr[i][2]);
    }
    for (int i = 1; i <= q; i++)
        cout << ans[i] << "\n";
}

Compilation message (stderr)

examination.cpp: In function 'void fqry(long long int, long long int)':
examination.cpp:27:14: 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]
   27 |     for (; x <= nen.size(); x += x & -x)
      |            ~~^~~~~~~~~~~~~
examination.cpp: In function 'void build()':
examination.cpp:33:23: 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]
   33 |     for (int i = 1; i <= nen.size(); i++)
      |                     ~~^~~~~~~~~~~~~
examination.cpp: In function 'long long int qry(long long int, long long int)':
examination.cpp:52:14: 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]
   52 |     for (; x <= nen.size(); x += x & -x)
      |            ~~^~~~~~~~~~~~~
examination.cpp:53:76: 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]
   53 |         for (int i = lower_bound(all(fake[x]), y) - fake[x].begin() + 1; i <= fake[x].size(); i += i & -i)
      |                                                                          ~~^~~~~~~~~~~~~~~~~

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