Submission #1037318

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037318		Thanhs	Examination (JOI19_examination)	C++14	100 / 100	233 ms	17080 KiB

examination

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define double long double
 
#define endl '\n'
#define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))
#define fi first
#define se second
#define all(x) x.begin(), x.end()
 
// mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
// int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}

const int NM = 2e5 + 5;
const int mod = 1e9 + 7;

struct BIT
{
    int b[NM], n = 2e5;
    void upd(int i, int v)
    {
        for (; i <= n; i += i & -i)
            b[i] += v;
    }
    int get(int i)
    {
        int res = 0;
        for (; i; i -= i & -i)
            res += b[i];
        return res;
    }
}bit;

struct o{
    int x, y, z, i, w;
    o(int x, int y, int z, int i, int w) : x(x), y(y), z(z), i(i), w(w){}
};

vector<o> v;
vector<int> ans;


void cdq(int l, int r)
{
    if (l == r)
        return;
    int m = l + r >> 1;
    cdq(l, m);
    cdq(m + 1, r);
    int a = l, b = m + 1, sum = 0;
    vector<pair<int, int>> record;
    vector<o> tmp;
    while (a <= m && b <= r)
    {
        if (v[a].y > v[b].y)
            bit.upd(v[a].z, v[a].w), sum += v[a].w, record.push_back({v[a].z, v[a].w}), tmp.push_back(v[a++]);
        else
            ans[v[b].i] += sum - bit.get(v[b].z), tmp.push_back(v[b++]);
    }
    while (a <= m)
        tmp.push_back(v[a++]);
    while (b <= r)
        ans[v[b].i] += sum - bit.get(v[b].z), tmp.push_back(v[b++]);
    for (int i = l; i <= r; i++)
        v[i] = tmp[i - l];
    for (auto i : record)
        bit.upd(i.fi, -i.se);
    vector<pair<int, int>> ().swap(record);
    vector<o> ().swap(tmp);
}

vector<int> nen;

int mp(int x)
{
    return lower_bound(nen.begin(), nen.end(), x) - nen.begin() + 1;
}

void solve()
{
    int n = v.size();
    sort(v.begin(), v.end(),[&](const o& a, const o& b){return a.x != b.x ? a.x > b.x : (a.y != b.y ? a.y < b.y : a.z < b.z);});
    for (auto t : v)
        nen.push_back(t.z);
    sort(nen.begin(), nen.end());
    nen.erase(unique(nen.begin(), nen.end()), nen.end());
    for (auto& t : v)
        t.z = mp(t.z);
    ans.resize(n);
    cdq(0, n - 1);
}

signed main()
{
    fastIO
    if (fopen("in.txt", "r")) 
    {
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    }
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        int s, t;
        cin >> s >> t;
        v.emplace_back(s, t, s + t, v.size(), 1);
    }
    for (int i = 1; i <= q; i++)
    {
        int x, y, z;
        cin >> x >> y >> z;
        v.emplace_back(x - 1, y - 1, z - 1, v.size(), 0);
    }
    solve();
    for (int i = n; i < n + q; i++)
        cout << ans[i] << endl;
}

Compilation message (stderr)

examination.cpp: In function 'void cdq(int, int)':
examination.cpp:53:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |     int m = l + r >> 1;
      |             ~~^~~
examination.cpp: In function 'int main()':
examination.cpp:104:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  104 |         freopen("in.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
examination.cpp:105:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |         freopen("out.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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