Submission #1272431

#	Time	Username	Problem	Language	Result	Execution time	Memory
1272431		doq	Examination (JOI19_examination)	C++20	0 / 100	636 ms	1114112 KiB

examination

#include<bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define ALL(x) (x).begin(),(x).end()
#define pb push_back
const int N = 2e5 + 5;
struct pp{
    int fi, se, th, o, id = 0;
} a[N];

struct po {
    int fi, se, id;
};

bool c1 (po a, po b){
    if(a.fi != b.fi) return a.fi > b.fi;
    return a.se > b.se;
}

int ans[N], q, n;
bool cmp(pp a, pp b) {
    if(a.fi != b.fi) return a.fi > b.fi;
    if(a.o != b.o) return a.o < b.o;
    if(a.se != b.se) return a.se > b.se;
}

struct BIT {
    int f[N * 3];
    void update(int id, int val) {
        for(; id > 0; id -= id & (-id)) f[id] += val;
    }
    int get(int id) {
        int res = 0;
        for(; id < N * 3; id += id & (-id)) res += f[id];
        return res;
    }
    void mem() {
        memset(f, 0, sizeof(f));
    }
}bit;

void dnc(int l, int r) {
    if(l == r) return;
    int m = (l + r) >> 1;
    dnc(l, m); dnc(m + 1, r);

    vector<po> v1, v2;
    for(int i = l; i <= m; i++) if(a[i].o == 0) v1.pb({a[i].se, a[i].th, i});
    for(int i = m + 1; i <= r; i++) if(a[i].o == 1) v2.pb({a[i].se, a[i].th, a[i].id});

    sort(ALL(v1), c1);
    sort(v2.begin(), v2.end(), c1);

    int id = 0;
    stack<int> st;
    for(int i = 0; i < sz(v2); i++){
        int fi = v2[i].fi, se = v2[i].se, idx = v2[i].id;
//        if(l == 1 && r == n + q) cout << idx << '\n';
        while(id < sz(v1) && v1[id].fi >= fi) {
//            if(idx == 1) cout << v1[id].fi << ' ' << fi << '\n';
            st.push(v1[id].se);
            bit.update(v1[id].se, 1);
            id++;
        }
        ans[idx] += bit.get(se);
    }
    while(st.size()) {
        int v = st.top();
        bit.update(v, -1);
        st.pop();
    }
}

vector<int> k, vx;
int id(int n) {
    return lower_bound(ALL(vx), n) - vx.begin() + 1;
}

void nen() {
    for(int i = 1; i <= n + q; i++) {
        k.pb(a[i].fi);
        k.pb(a[i].se);
        k.pb(a[i].th);
    }
    sort(ALL(k));
    for(int i = 0; i < sz(k); i++) if(i == 0 || k[i] != k[i - 1]) vx.pb(k[i]);
    for(int i = 1; i <= n + q; i++) {
        a[i].fi = id(a[i].fi);
        a[i].se = id(a[i].se);
        a[i].th = id(a[i].th);
    }
}
main() {
    ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0);
    #define task "ANHDEP"
    freopen(task ".inp", "r", stdin);
    freopen(task ".out", "w", stdout);

    cin >> n >> q;
    for(int i = 1; i <= n; i++) {
        cin >> a[i].fi >> a[i].se;
        a[i].th = a[i].fi + a[i].se;
        a[i].o = 0;
    }
    for(int i = 1; i <= q; i++) {
        cin >> a[i + n].fi >> a[i + n].se >> a[i + n].th;
        a[i + n].id = i;
        a[i + n].o = 1;
    }
    nen();
    sort(a + 1, a + n + q + 1, cmp);
//    for(int i = 1; i <= n + q; i++)
//        cout << a[i].fi << ' ' << a[i].se << ' ' << a[i].th << ' ' << a[i].id << '\n';
    dnc(1, n + q);
    for(int i = 1; i <= q; i++) cout << ans[i] << '\n';
}

Compilation message (stderr)

examination.cpp:93:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   93 | main() {
      | ^~~~
examination.cpp: In function 'bool cmp(pp, pp)':
examination.cpp:25:1: warning: control reaches end of non-void function [-Wreturn-type]
   25 | }
      | ^
examination.cpp: In function 'int main()':
examination.cpp:96:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   96 |     freopen(task ".inp", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:97:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |     freopen(task ".out", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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