Submission #477820

#	Time	Username	Problem	Language	Result	Execution time	Memory
477820		Mike4235	Examination (JOI19_examination)	C++17	100 / 100	1431 ms	69320 KiB

examination

/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/
// only when really needed

/* GNU G++17 7.3.0: No long long for faster code
   GNU G++17 9.2.0 (64 bit, msys 2): Long long only for faster code */
 
#include <bits/stdc++.h>
  
#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
#define int long long

#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pb push_back
 
/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/
 
#define PI 3.1415926535897932384626433832795
#define INF 1000000000000000000
#define MOD 1000000007
#define MOD2 1000000009
#define EPS 1e-6

using namespace std;

struct Point{
    int x, y, z, id, ans;
    bool operator< (Point const& o) {
        if (x != o.x) return x > o.x;
        if (y != o.y) return y < o.y;
        return z < o.z;
    }
};

const int k = 6e5;

int n, q;
map<int, int> mp;
int res[100005], fentree[600005];
vector<Point> v;

void update(int i, int val) {
    for (; i <= k; i += i & -i) fentree[i] += val;
}

int get(int i) {
    int res = 0;
    for (; i; i -= i & -i) res += fentree[i];
    return res;
}

void cdq(int l, int r) {
    if (l == r) return;
    int m = (l + r)/2;
    cdq(l, m); cdq(m + 1, r);

    // cout << l << " " << r << "\n";
    // for1(i,l,r) cout << v[i].x << " " << v[i].y << " " << v[i].z << "\n";
    vector<Point> st;
    vector<int> roll;
    int a = l, b = m + 1, sum = 0;

    while (a <= m && b <= r) {
        if (v[a].y > v[b].y) {
            if (!v[a].id) {
                sum++;
                update(v[a].z, 1);
                roll.push_back(v[a].z);
            }
            st.push_back(v[a++]);
        }
        else {
            if (v[b].id) res[v[b].id] += sum - get(v[b].z);
            // cout << v[b].x << " " << v[b].y << " " << v[b].z << " " << v[b].id << " " << sum - get(v[b].z) << "\n";
            st.push_back(v[b++]);
        }
    }

    while (a <= m) st.push_back(v[a++]);
    while (b <= r) {
        if (v[b].id) res[v[b].id] += sum - get(v[b].z);
        // cout << v[b].x << " " << v[b].y << " " << v[b].z << " " << v[b].id << " " << sum - get(v[b].z) << "\n";
        st.push_back(v[b++]);
    }
    // cout << "\n";

    for1(i,l,r) v[i] = st[i - l];
    for (auto x : roll) update(x, -1);
}

signed main() {
    
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    // freopen("cf.inp", "r", stdin);
    // freopen("cf.out", "w", stdout);

    cin >> n >> q;
    for1(i,1,n) {
        int a, b;
        cin >> a >> b;
        v.push_back({a, b, a + b, 0, 0});
        mp[a] = 0;
        mp[b] = 0;
        mp[a + b] = 0;
    }

    for1(i,1,q) {
        int x, y, z;
        cin >> x >> y >> z;
        x--; y--; z--;
        v.push_back({x, y, z, i, 0});
        mp[x] = 0;
        mp[y] = 0;
        mp[z] = 0;
    }

    int cur = 0;
    for (auto &p : mp) p.second = ++cur;
    for (auto &p : v) p.x = mp[p.x], p.y = mp[p.y], p.z = mp[p.z];

    sort(v.begin(), v.end());

    cdq(0, n + q - 1);

    // for (auto p : v) cout << p.x << " " << p.y << " " << p.z << " " << p.id << " " << p.ans << "\n";
    // cout << "\n";
    // for (auto p : s) cout << p.x << " " << p.y << " " << p.z << " " << p.id << " " << p.ans << "\n";
    // cout << "\n";

    for1(i,1,q) cout << res[i] << "\n";
    
}

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