Submission #1283062

#	Time	Username	Problem	Language	Result	Execution time	Memory
1283062		nottete	Examination (JOI19_examination)	C++20	100 / 100	576 ms	14484 KiB

examination

#include <bits/stdc++.h>
using namespace std;

struct FT {
    vector<int> v;
    int sz;
    FT() {}
    FT(int n) :  v(n), sz(n) {}

    int sum(int r) {
        int ret = 0;
        for(; r >= 0; r = (r & (r + 1)) - 1) ret += v[r];
        return ret;
    }

    int sum_left(int r) {
        int x = sum(sz - 1);
        if(x != 0) x -= sum(r - 1);
        return x;
    }

    void add(int idx, int d) {
        for(; idx < sz; idx = idx | (idx + 1)) v[idx] += d;
    }

};

struct Point {
    int a, b, c, t;
};

vector<int> sol;
vector<Point> v;
vector<int> c;
int mc;

bool cmp1(Point a, Point b) {
    if(a.a > b.a) return true;
    if(a.a < b.a) return  false;

    if(a.b > b.b) return true;
    if(a.b < b.b) return false;

    if(a.c > b.c) return true;
    if(a.c < b.c) return false;

    return a.t < b.t;
}

bool cmp2(pair<Point, int>& a, pair<Point, int>& b) {
    if(a.first.b > b.first.b) return true;
    if(a.first.b < b.first.b) return  false;

    if(a.first.c > b.first.c) return true;
    if(a.first.c < b.first.c) return  false;

    if(a.second < b.second) return true;
    if(a.second > b.second) return false;

    return a.first.t < b.first.t;
}

FT fenwick;

void dcq(int l, int r) {
    if(l == r) return;
    else {
        int mid = (l + r) / 2;
        dcq(l, mid);
        dcq(mid + 1, r);
        vector<pair<Point,int>> tmp(r - l + 1);
        for(int i = l; i <= mid; i++) tmp[i - l] = {v[i], 0};
        for(int i = mid + 1; i <= r; i++) tmp[i - l] = {v[i], 1};
        sort(tmp.begin(), tmp.end(), cmp2);

        for(auto[p, x] : tmp) {
            //cout << c[p.a] << " " << c[p.b] << " " << c[p.c] << " " << p.t << " " << x << "\n";
            if(p.t < 0 && x == 0) {
                //cout << "Fenwick: " << c[p.c] << "\n";
                fenwick.add(p.c, 1);
            }

            if(p.t > 0 && x == 1) {
                sol[p.t - 1] += fenwick.sum_left(p.c);
                //cout << "Adding: " << p.t - 1 << " " << fenwick.sum_left(p.c) << "\n";
            }
        }
        
        for(auto[p, x] : tmp) {
            if(p.t < 0 && x == 0) {
                fenwick.add(p.c, -1);
            }
        }
        //cout << "=============\n";
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    sol.assign(m, 0);
    v.assign(n + m, {});
    c.assign((n + m) * 3, 0);
    for(int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        v[i].a = a;
        v[i].b = b;
        v[i].c = a + b;
        v[i].t = -i - 1;
        c[3*i] = a;
        c[3*i+1] = b;
        c[3*i+2] = a + b;
    }

    for(int i = 0; i < m; i++) {
        cin >> v[n + i].a >> v[n + i].b >> v[n + i].c;
        v[n + i].t = i + 1;
        c[3*(i + n)] = v[n+i].a;
        c[3*(i + n)+1] = v[n+i].b;
        c[3*(i + n)+2] = v[n+i].c;
    }
    sort(c.begin(), c.end());
    c.resize(unique(c.begin(), c.end()) - c.begin());
    for(int i = 0; i < n + m; i++) {
        v[i].a = lower_bound(c.begin(), c.end(), v[i].a) - c.begin();
        v[i].b = lower_bound(c.begin(), c.end(), v[i].b) - c.begin();
        v[i].c = lower_bound(c.begin(), c.end(), v[i].c) - c.begin();
    }
    mc = c.size();
    fenwick = FT(mc);

    sort(v.begin(), v.end(), cmp1);
    dcq(0, v.size() - 1);
    for(int i : sol) cout << i << "\n";
} 

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