Submission #1288550

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288550		huudai	Examination (JOI19_examination)	C++20	100 / 100	252 ms	11472 KiB

examination

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll,ll>
#define mp make_pair
#define pb push_back

#define BIT(x,i) (((x)>>(i))&1)
#define MASK(i) (1LL<<(i))  

template<typename T1, typename T2> bool minimize(T1 &a, T2 b)
    {if(a>b) a=b; else return 0; return 1;}
template<typename T1, typename T2> bool maximize(T1 &a, T2 b)
    {if(a<b) a=b; else return 0; return 1;}

#define file "task"

const int maxn = 2e5 + 5;
const int MOD  = 1e9 + 7;
const int oo   = 1e9;
const ll  OO   = 1e18;

int n, q;
pii a[maxn];
int ans[maxn];
vector<int> comnum;

struct fenwick{
    int fw[maxn];
    fenwick(){
        memset(fw, 0, sizeof(fw));
    }

    void update(int id, int w){
        for(;id <= n + q; id += id & -id) 
            fw[id] += w;
    }

    int get(int id){
        int ret = 0;
        for(;id > 0; id -= id & -id) 
            ret += fw[id];
        return ret;
    }
} fw;

struct item{
    int x, y, z, id;
    item(){}
    item(int x, int y, int z, int id) : x(x), y(y), z(z), id(id){}
};
vector<item> query;

bool cmp(item a, item b){
    if(a.z == b.z) return a.id < b.id;
    return a.z > b.z;
}

void input(){
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> a[i].fi >> a[i].se;
    }
}

void merge(int l, int m, int r){
    vector<item> p1, p2;
    for(int i = l; i <= m; i++){
        if(query[i].id == 0) 
            p1.pb(item(query[i].x, query[i].y, query[i].x, 0));
    }
    for(int i = m + 1; i <= r; i++){
        if(query[i].id) 
            p2.pb(item(query[i].x, query[i].y, query[i].x, query[i].id));
    }

    sort(p1.begin(), p1.end(), cmp);
    sort(p2.begin(), p2.end(), cmp);
    int i = 0;
    for(auto [x, y, z, id] : p2){
        while(i < p1.size() && p1[i].x >= x){
            fw.update(p1[i].y, 1);
            i++;
        }
        ans[id] += fw.get(n + q) - fw.get(y - 1);
    }
    for(int j = i - 1; j >= 0; j--)
        fw.update(p1[j].y, - 1);

}

void dnc(int l, int r){
    if(l == r) return;
    int m = (l + r) >> 1;
    dnc(l, m);
    dnc(m + 1, r);
    merge(l, m, r);
}

void proc(){
    for(int i = 1; i <= n; i++){
        comnum.pb(a[i].se);
        query.pb(item(a[i].fi, a[i].se, a[i].fi + a[i].se, 0));
    }

    for(int i = 1; i <= q; i++){
        int x, y, z; cin >> x >> y >> z;
        comnum.pb(y);
        query.pb(item(x, y, z, i));
    }

    sort(comnum.begin(), comnum.end());
    comnum.erase(unique(comnum.begin(), comnum.end()), comnum.end());
    for(auto &[x, y, z, id] : query)
        y = lower_bound(comnum.begin(), comnum.end(), y) - comnum.begin() + 1;

    sort(query.begin(), query.end(), cmp);
    dnc(0, n + q - 1);

    for(int i = 1; i <= q; i++){
        cout << ans[i] << '\n';
    }
}

signed main(){
    cin.tie(nullptr)->sync_with_stdio(0); cout.tie(nullptr);    
    if(fopen(file".inp", "r")){
        freopen(file".inp", "r", stdin);
        freopen(file".out", "w", stdout);
    }
    
    input();
    proc();

    return 0;
}

Compilation message (stderr)

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

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