oj.uz

Submission #888082

# Submission time Handle Problem Language Result Execution time Memory
888082 2023-12-15T23:47:05 Z vjudge1 Examination (JOI19_examination) C++17
0 / 100
 196 ms 11016 KB 
#include<bits/stdc++.h>
using namespace std;
struct st {
    int x, y, z, i;
};
vector<st> v;
struct fenwick {
    int t[400010];
    void upd(int n, int x) {
        for(;n<=4e5;n=n|(n+1))
            t[n]+=x;
    }
    int q(int n) {
        int x = 0;
        for(;n>=0;n=(n&(n+1))-1)
            x+=t[n];
        return x;
    }
    int Q(int x) {
        return q(4e5)-q(x-1);
    }
} A,B;
int ans[100100];
map<int,int> mp;
int main() {
    cin.sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    for(int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        mp[a], mp[b];
        v.push_back({a,b,a+b,0});
    }
    for(int i = 1; i <= q; i++) {
        int x,y,z;
        cin >> x >> y>> z;
        mp[x],mp[y];
        v.push_back({x,y,z,i});
    }
    sort(v.begin(),v.end(),[](st a, st b) {
        return (a.z-b.z?a.z>b.z:a.i<b.i);
    });
    int cnt = 0;
    for(auto &i: mp)
        i.second=cnt++;
    cnt=0;
    for(auto i: v)
        if(i.i)
            ans[i.i]=A.Q(mp[i.x])+B.Q(mp[i.y])-cnt;
        else
            A.upd(mp[i.x],1),B.upd(mp[i.y],1),cnt++;
    for(int i = 1; i <= q; i++)
        cout << ans[i] << '\n';
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 196 ms 11016 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 196 ms 11016 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -