Submission #768742

#	Time	Username	Problem	Language	Result	Execution time	Memory
768742		raysh07	Examination (JOI19_examination)	C++17	100 / 100	658 ms	62096 KiB

examination

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18

mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());

struct query{
    int x, y, s, i;
};

struct score{
    int x, y, s;
};

const int N = 1e5 + 69;
int ans[N], n, q;
query Q[N];
score A[N];
int f[4 * N][2];
int mx;

bool c1(score a, score b){
    return a.s > b.s;
}

bool c2(query a, query b){
    return a.s > b.s;
}

void upd(int x, int j){
    for (int i = x; i <= mx; i += i & (-i)){
        f[i][j]++;
    }
}

int query(int x, int j){
    int res = 0;
    for (int i = x; i; i -= i & (-i)){
        res += f[i][j];
    }
    return res;
}

void Solve() 
{
    cin >> n >> q;
    
    set <int> st;
    
    for (int i = 1; i <= n; i++){
        int x, y; cin >> x >> y;
        
        A[i].x = x;
        A[i].y = y;
        A[i].s = x + y;
        
        st.insert(A[i].x);
        st.insert(A[i].y);
    }
    
    for (int i = 1; i <= q; i++){
        cin >> Q[i].x >> Q[i].y >> Q[i].s;
        
        Q[i].s = max(Q[i].s, Q[i].x + Q[i].y);
        Q[i].i = i;
        st.insert(Q[i].x);
        st.insert(Q[i].y);
    }
    
    sort(A + 1, A + n + 1, c1);
    sort(Q + 1, Q + q + 1, c2);
    
    map <int, int> mp;
    int pr = 0;
    for (auto x : st){
        mp[x] = ++pr;
    }
    mx = pr;
    
    for (int i = 1; i <= n; i++){
        A[i].x = mp[A[i].x];
        A[i].y = mp[A[i].y];
    }
    
    for (int i = 1; i <= q; i++){
        Q[i].x = mp[Q[i].x];
        Q[i].y = mp[Q[i].y];
    }
    
    int ptr = 1;
    
    // for (int i = 1; i <= n; i++){
    //     cout << A[i].s << " ";
    // }
    // cout << "\n";
    for (int i = 1; i <= q; i++){
        while (ptr <= n && A[ptr].s >= Q[i].s){
           // cout << "ADDED " << A[ptr].x << " " << A[ptr].y << "\n";
            upd(A[ptr].x, 0);
            upd(A[ptr].y, 1);
            ptr++;
        }
        
      //  cout << Q[i].i << " " << ptr << " " << Q[i].x << " " << Q[i].y << " ";
        int x = query(Q[i].x - 1, 0); 
        x += query(Q[i].y - 1, 1);
        ans[Q[i].i] = ptr - 1 - x;
    }
    
    for (int i = 1; i <= q; i++) cout << ans[i] << "\n";
}

int32_t main() 
{
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int t = 1;
  //  cin >> t;
    for(int i = 1; i <= t; i++) 
    {
        //cout << "Case #" << i << ": ";
        Solve();
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
    return 0;
}

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