Submission #674168

#	Time	Username	Problem	Language	Result	Execution time	Memory
674168		Cookie	Examination (JOI19_examination)	C++14	100 / 100	1355 ms	119276 KiB

examination

#include<bits/stdc++.h>

#include<fstream>
//#include "factories.h"

using namespace std;
ifstream fin("sus.in");
ofstream fout("sus.out");
#define ll long long
#define vt vector
#define pb push_back
#define fi first
#define se second
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define pii pair<int, int>
#define pll pair<ll, ll>
const int x[4] = {1, -1, 0, 0};
const int y[4] = {0, 0, 1, -1};
#define int long long
const int mxn = 1e5, sq = 800;
int block[mxn + 1];
int n, q;
vt<ll>compx, compy;
struct BIT{
    int bit[3 * mxn + 1];
    void upd(int p, int v){
        while(p <= 3 * mxn){
            bit[p] += v; p += p & (-p);
        }
    }
    int get(int p){
        int ans = 0;
        while(p){
            ans += bit[p];
            p -= p & (-p);
        }
        return(ans);
    }
};
BIT bit[sq + 1];
struct ob{
    int x, y, id;
    bool operator <(const ob &b){
        return(x < b.x);
    }
};
vt<ob>v;
struct qq{
    ll x, y, z; int id;
    bool operator <(const qq &b){
        return(z > b.z);
    }
};
qq a[mxn + 1];
int ans[mxn + 1];
qq queries[mxn + 1];
bool used[mxn + 1];
void upd(int id, int v){
    bit[block[id]].upd(v, 1);
}
int solve(int l, int r, int y){
    if(l > r)return(0);
    int bl = block[l], br = block[r];
    int ans  =0;
    if(bl == br){
        //for(int i = 1; i <= n; i++)cout << used[i] << " ";
        //cout << "\n";
        for(int i = l; i <= r; i++)ans += (v[i - 1].y >= y && used[i]);
        //cout << ans << "\n";
        return(ans);
    }
    for(int i = l; i < sq * (bl + 1); i++){
        
        ans += (v[i - 1].y >= y && used[i]);
    }
    for(int i = br * sq; i <= r; i++)ans += (v[i - 1].y >= y && used[i]);
    for(int i = bl + 1; i < br; i++){
        ans += bit[i].get(3 * mxn) - bit[i].get(y - 1);
    }
    return(ans);
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for(int i = 1; i <= n; i++)block[i] = i / sq;
    
    forr(i, 0, n){
        cin >> a[i].x >> a[i].y; a[i].z = a[i].x + a[i].y;
        compx.pb(a[i].x); compy.pb(a[i].y);
        v.pb({a[i].x, a[i].y, i});
    }
    sort(v.begin(), v.end());
    //for(auto [x, y, id]: v)cout << x << " " << y << " " << id << "\n";
    for(int i = 0; i < v.size(); i++){
        a[v[i].id].id = i + 1;
    }
    sort(a, a + n);
    forr(i, 0, q){
        cin >> queries[i].x >> queries[i].y >> queries[i].z; queries[i].id = i;
    }
    sort(queries, queries + q);
    sort(compx.begin(), compx.end());
    sort(compy.begin(), compy.end());
    int mx = 0;
    forr(i, 0, n){
        a[i].x = lower_bound(compx.begin(), compx.end(), a[i].x) - compx.begin() + 1;
        a[i].y = lower_bound(compy.begin(), compy.end(), a[i].y) - compy.begin() + 1;
        v[i].y = lower_bound(compy.begin(), compy.end(), v[i].y) - compy.begin() + 1;
        
    }
    forr(i, 0, q){
        queries[i].x = lower_bound(compx.begin(), compx.end(), queries[i].x) - compx.begin() + 1;
        queries[i].y = lower_bound(compy.begin(), compy.end(), queries[i].y) - compy.begin() + 1;
    }
    int l = 0;
    for(int i = 0; i < q; i++){

        while(l < n && a[l].z >= queries[i].z){
            upd(a[l].id, a[l].y); used[a[l].id] = true;
            l++;
        }
        
        //cout << l << " ";
        //assert(a[queries[i].x].x == )
        ans[queries[i].id] = solve(queries[i].x, n, queries[i].y);
    }
    forr(i, 0, q)cout << ans[i] << "\n";
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:95:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<ob>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for(int i = 0; i < v.size(); i++){
      |                    ~~^~~~~~~~~~
examination.cpp:105:9: warning: unused variable 'mx' [-Wunused-variable]
  105 |     int mx = 0;
      |         ^~

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