Submission #120229

#	Time	Username	Problem	Language	Result	Execution time	Memory
120229		oolimry	Examination (JOI19_examination)	C++14	100 / 100	1002 ms	35924 KiB

examination

#include <bits/stdc++.h>

using namespace std;
typedef pair<int,int> ii;
struct query{
    int x, y, z, id;
};
bool comp(query a, query b){
    return a.z > b.z;
}
bool comp2(ii a, ii b){
    return a.first + a.second > b.first + b.second;
}

class SegmentTree{
public:

    int n;
    vector<int> tree;

    void create(int nn){
        n = nn;
        for(int i = 0;i < 2 * n + 5;i++){
            tree.push_back(0);
        }
    }

    void update(int i){
        i += n;
        while(i > 0){
            tree[i]++;
            i >>= 1;
        }
    }

    int query(int l, int r){
        int ans = 0;
        for(l += n,r += n;l < r;l >>= 1, r >>= 1){
            if(l & 1){
                ans += tree[l];
                l++;
            }
            if(r & 1){
                r--;
                ans += tree[r];
            }
        }
        return ans;
    }
};

int main()
{
    //freopen("i.txt","r",stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;
    map<int,int> dis;
    ii arr[n];
    for(int i = 0;i < n;i++){
        cin >> arr[i].first >> arr[i].second;
        dis[arr[i].first] = 0;
        dis[arr[i].second] = 0;
    }

    query queries[m];
    for(int i = 0;i < m;i++){
        int x, y, z;
        cin >> x >> y >> z;
        z = max(z, x + y);
        query q;
        q.z = z;
        q.y = y;
        q.x = x;
        dis[x] = 0;
        dis[y] = 0;
        q.id = i;
        queries[i] = q;
    }
    int cc = 0;
    for(map<int,int>::iterator it = dis.begin();it != dis.end();it++){
        it->second = cc;
        cc++;
    }
    sort(queries,queries+m,comp);
    sort(arr,arr+n,comp2);
    SegmentTree x;
    SegmentTree y;
    x.create(dis.size());
    y.create(dis.size());
    int ans[m];
    int c = 0;
    for(int i = 0;i < m;i++){
        //cout << queries[i].z << ": ";
        while(true){
            if(c == n) break;
            if(arr[c].first + arr[c].second < queries[i].z) break;
            //cout << arr[c].first << " " << arr[c].second << "|";
            x.update(dis[arr[c].first]);
            y.update(dis[arr[c].second]);
            c++;
        }
        ans[queries[i].id] = c - x.query(0,dis[queries[i].x]) - y.query(0,dis[queries[i].y]);
        //cout << "\n";
    }
    for(int i = 0;i < m;i++){
        cout << ans[i] << "\n";
    }
    return 0;
}

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