Submission #1106734

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106734		luvna	Examination (JOI19_examination)	C++14	100 / 100	261 ms	21748 KiB

examination

#include<bits/stdc++.h>

#define MASK(i) (1 << (i))
#define pub push_back
#define all(v) v.begin(), v.end()
#define compact(v) v.erase(unique(all(v)), end(v))
#define pii pair<int,int>
#define fi first
#define se second
#define endl "\n"
#define sz(v) (int)(v).size()

using namespace std;

template<class T> bool minimize(T& a, T b){if(a > b) return a = b, true;return false;}
template<class T> bool maximize(T& a, T b){if(a < b) return a = b, true;return false;}

typedef long long ll;
typedef long double ld;

mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll rand_range(ll l, ll r){return uniform_int_distribution<ll>(l, r)(rng);}

const int N = 1e6 + 15;

struct node{
    int x, y, z, id;
};

bool cmp(node a, node b){
    return (a.z == b.z) ? a.id < b.id : a.z > b.z;
}

bool cmp1(node a, node b){
    return a.x > b.x;
}

int n, q;
vector<node> evt;
vector<int> compress;
int bit[N];

void update(int idx, int val){
    for(;idx <= sz(compress); idx += (idx & (-idx))) bit[idx] += val;
}

int get(int idx){ int res = 0;
    for(;idx; idx -= (idx & (-idx))) res +=  bit[idx];
    return res;
}

int ans[N];
deque<int> save;

void cdq(int l, int r){
    if(l >= r) return;

    int mid = (l+r) >> 1;

    vector<node> upd, ask;
    for(int i = l; i <= mid; i++) if(evt[i].id == -1) upd.pub(evt[i]);
    for(int i = mid+1; i <= r; i++) if(evt[i].id != -1) ask.pub(evt[i]);

    sort(all(upd),cmp1); sort(all(ask),cmp1);

    for(int i = 0, j = 0; i < sz(ask); i++){
        while(j < sz(upd) && upd[j].x >= ask[i].x){
            update(upd[j].y, 1);
            save.push_back(upd[j].y);
            j++;
        }
        ans[ask[i].id] += get(sz(compress)) - get(ask[i].y-1);
    }

    while(!save.empty()) update(save.back(), -1), save.pop_back();

    cdq(l,mid);
    cdq(mid+1,r);
}

void solve(){
    cin >> n >> q;

    for(int i = 1; i <= n; i++){
        int x, y; cin >> x >> y;
        evt.pub({x,y,x+y,-1});
        compress.pub(y);
    }

    for(int i = 1; i <= q; i++){
        int x, y, z; cin >> x >> y >> z;
        evt.pub({x,y,z,i});
        compress.pub(y);
    }

    sort(all(compress)); compact(compress);
    for(int i = 0; i < sz(evt); i++) evt[i].y = lower_bound(all(compress), evt[i].y) - compress.begin() + 1;
    sort(all(evt),cmp);

    //for(auto [x, y, z, id] : evt) cout << id << "   " << x << " " << y << " " << z << endl;

    cdq(0,sz(evt)-1);

    for(int i = 1; i <= q; i++) cout << ans[i] << endl;
}

signed main(){
    ios_base::sync_with_stdio(NULL);
    cin.tie(0); cout.tie(0);

    #define task "task"

    if(fopen(task".INP", "r")){
        freopen(task".INP", "r", stdin);
        freopen(task".OUT", "w", stdout);
    }

    int t; t = 1; //cin >> t;
    while(t--) solve();
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:114:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  114 |         freopen(task".INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:115:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         freopen(task".OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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