Submission #997844

#	Time	Username	Problem	Language	Result	Execution time	Memory
997844		khanhphucscratch	Examination (JOI19_examination)	C++14	100 / 100	2530 ms	77516 KiB

examination

#include<bits/stdc++.h>
using namespace std;
struct Point
{
    vector<int> coordinate;
    int idx; //idx = 0: no query
};
int m = 2e5, bit[200005], ans[100005];
void update(int p, int v)
{
    for(int i = p; i <= m; i += i & (-i)) bit[i] += v;
}
int query(int p)
{
    if(p <= 0) return 0;
    return bit[p] + query(p - (p & (-p)));
}
bool cmp(Point x, Point y)
{
    for(int i = x.coordinate.size()-1; i >= 0; i--) if(x.coordinate[i] != y.coordinate[i]) return x.coordinate[i] < y.coordinate[i];
    return x.idx < y.idx;
}
void solve(vector<Point> p, int k)
{
    if(p.size() == 1) return;
    sort(p.begin(), p.end(), cmp);
    while(k > 2 && p[0].coordinate[k-1] == p[p.size()-1].coordinate[k-1]){
        for(int i = 0; i < p.size(); i++) p[i].coordinate.pop_back();
        k--;
    }
    /*cout<<"A"<<k<<endl;
    for(Point i : p){
        cout<<i.idx<<" ";
        for(int j = 0; j < k; j++) cout<<i.coordinate[j]<<" ";
        cout<<endl;
    }*/
    if(k == 2){ //Solve in O(n log n)
        for(Point i : p){
            if(i.idx == 0) update(i.coordinate[0], 1);
            else{
                ans[i.idx] += query(i.coordinate[0]);
                //cout<<"+"<<i.idx<<" "<<query(i.coordinate[0])<<endl;
            }
        }
        for(Point i : p) if(i.idx == 0) update(i.coordinate[0], -1);
        return;
    }
    int mid = ((int)p.size()+1)/2 - 1;
    vector<Point> le, ri;
    for(int i = 0; i <= mid; i++) le.push_back(p[i]);
    for(int i = mid+1; i < p.size(); i++) ri.push_back(p[i]);
    solve(le, k); solve(ri, k);
    vector<Point> newp;
    for(int i = 0; i <= mid; i++) if(p[i].idx == 0){
        p[i].coordinate.pop_back();
        newp.push_back(p[i]);
    }
    for(int i = mid+1; i < p.size(); i++) if(p[i].idx > 0){
        p[i].coordinate.pop_back();
        newp.push_back(p[i]);
    }
    solve(newp, k-1);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, q;
    cin>>n>>q;
    vector<Point> p(n+q);
    for(int i = 0; i < n; i++){
        int x, y;
        cin>>x>>y;
        x = 1000000000-x; y = 1000000000-y;
        p[i].coordinate = {x, y, x+y};
        p[i].idx = 0;
    }
    for(int i = 0; i < q; i++){
        int x, y, z;
        cin>>x>>y>>z;
        x = 1000000000-x; y = 1000000000-y; z = 2000000000 - z;
        p[n+i].coordinate = {x, y, z};
        p[n+i].idx = i+1;
    }
    for(int j = 0; j < 3; j++){
        set<int> wtf; int sz = 0;
        unordered_map<int, int> f;
        for(int i = 0; i < p.size(); i++) wtf.insert(p[i].coordinate[j]);
        for(int i : wtf) f[i] = ++sz;
        for(int i = 0; i < p.size(); i++) p[i].coordinate[j] = f[p[i].coordinate[j]];
    }
    solve(p, 3);
    for(int i = 1; i <= q; i++) cout<<ans[i]<<'\n';
}

Compilation message (stderr)

examination.cpp: In function 'void solve(std::vector<Point>, int)':
examination.cpp:28:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |         for(int i = 0; i < p.size(); i++) p[i].coordinate.pop_back();
      |                        ~~^~~~~~~~~~
examination.cpp:51:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int i = mid+1; i < p.size(); i++) ri.push_back(p[i]);
      |                        ~~^~~~~~~~~~
examination.cpp:58:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |     for(int i = mid+1; i < p.size(); i++) if(p[i].idx > 0){
      |                        ~~^~~~~~~~~~
examination.cpp: In function 'int main()':
examination.cpp:88:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |         for(int i = 0; i < p.size(); i++) wtf.insert(p[i].coordinate[j]);
      |                        ~~^~~~~~~~~~
examination.cpp:90:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Point>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   90 |         for(int i = 0; i < p.size(); i++) p[i].coordinate[j] = f[p[i].coordinate[j]];
      |                        ~~^~~~~~~~~~

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