Submission #1097730

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097730		vjudge1	Examination (JOI19_examination)	C++17	100 / 100	479 ms	61136 KiB

examination

#include <bits/stdc++.h>

#define ll long long

using namespace std;
const int N = 1e5  + 2;
// int num_node = 0;
int n , q , m;
pair < ll , ll > a[N + 2];
vector < ll > vt; 
bool cmp_1(pair < int , int > g , pair < int , int > h){
    return g.first < h.first;
}
bool cmp_2(pair < int , int > g , pair < int , int > h){
    return g.first < h.first;
}
struct per{
    vector <pair < int , int > > bit[N * 4 + 2];
    void update(int id , int timer){
        while(id <= m){
            if(bit[id].empty())bit[id].push_back({timer , 1});
            else{
                int cur = bit[id].back().second;
                bit[id].push_back({timer , cur + 1});
            }
            id += id &(-id);
        }
    }
    int get(int id , int timer){
        int ans = 0;
        while(id  > 0){
            if(bit[id].size()){
                int k = upper_bound(bit[id].begin() , bit[id].end() , make_pair(timer , 0), cmp_1) - bit[id].begin();
                k--;
                if(k >= 0){
                    ans += bit[id][k].second;
                }
            }
            id -= id &(-id);
        }
        return ans;
    }
}BIT_ONE ,BIT_TWO;
int get_one(ll l , int timer_l , int timer_r){
    int k = upper_bound(vt.begin() , vt.end() , l) - vt.begin();
    if(k == 0)return 0;
   return  BIT_ONE.get(m , timer_r) - BIT_ONE.get(k - 1 , timer_r) + BIT_ONE.get(k - 1 , timer_l - 1) - BIT_ONE.get(m , timer_l - 1);
}
int get_two(ll c , int timer_l , int timer_r){
    int k = upper_bound(vt.begin() , vt.end() , c) - vt.begin();
     if(k == 0)return 0;
    return BIT_TWO.get(m , timer_r) - BIT_TWO.get(k - 1 , timer_r) + BIT_TWO.get(k - 1 , timer_l - 1) - BIT_TWO.get(m , timer_l - 1);
}
struct qq{
    ll t , c;
    int id;
};
vector < qq > query[N + 2];
int ans[N + 2];
void pre(){
        for(int  i= 1; i <= n ; i ++){
            vt.push_back(a[i].second);
            vt.push_back(a[i].first + a[i].second);
        }
        sort(vt.begin() , vt.end());
        vt.erase(unique(vt.begin() , vt.end()) , vt.end());
        m= vt.size();
        for(int i = 1 ; i <= n; i ++){
            int k = upper_bound(vt.begin() , vt.end() , a[i].second) - vt.begin();
            BIT_ONE.update(k , i);
            k = upper_bound(vt.begin() , vt.end() , a[i].first + a[i].second)- vt.begin();
            BIT_TWO.update(k , i);
          //  cout << get_two(100 , 1 , n) << ' ';
        }
       // for(auto v: vt)cout <<v << ' ';
       // cout << BIT_ONE.get(m , n) -BIT_ONE.get(k - 1 , n) <<  '\n';
       // cout <<'\n';
}
int bin(ll t , ll c , int i){
    int l = i;
    int r = n ;
    while(l <= r){
        int mid = (l + r) / 2;
        if(c - a[mid].first >= t){
            l = mid + 1;
        }
        else r = mid - 1;
    }
    return l  - 1;

}
void solve() {
    cin >> n >> q;
    for(int i = 1; i <= n ; i ++){
        cin >> a[i].first >> a[i].second;
    }
    sort(a  + 1 , a + n + 1);
    for(int i = 1 ; i <= q ; i ++){
        ll s ,  t , c;
        cin >> s >> t >> c;
       int k = lower_bound(a +  1 , a + n + 1, make_pair(s , 0), cmp_2)  - a; 
        query[k].push_back({t , c , i});
        vt.push_back(t);
        vt.push_back(c);
       
    }
      pre();
    for(int  i =n ;i >= 1; i --){
        for(auto cur : query[i]){
            int kl = bin(cur.t , cur.c , i);
            if(kl >= i){
                ans[cur.id] += get_two(cur.c , i , kl);
            }
            if(kl < n){
                ans[cur.id] += get_one(cur.t , kl + 1 , n);
            }
        }
    }
    for(int  i = 1 ; i <= q; i ++){
        cout << ans[i] << '\n';
    }
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0);
    
    #define _ "examination"
    if (fopen(_ "inp", "r")) {
        freopen(_ "inp", "r", stdin);
        freopen(_ "out", "w", stdout);
    }
    
    solve();
}

Compilation message (stderr)

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

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