Submission #881870

#	Time	Username	Problem	Language	Result	Execution time	Memory
881870		dimashhh	Examination (JOI19_examination)	C++17	100 / 100	292 ms	58132 KiB

examination

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 7e5 + 10, MOD = 1e9 + 7;

int n,q,s[N],t[N],x[N],y[N],z[N],sm[N],res[N],X[N],Y[N],Z[N];
vector<int> a,p,qq;
struct segtree{
    int t[N * 4];
    void build(int v = 1,int tl = 1,int tr = N){
        t[v] =0 ;
        if(tl == tr) return;
        int tm = (tl + tr) >> 1;
        build(v + v,tl,tm);
        build(v + v + 1,tm + 1,tr);
    }
    void upd(int pos,int val,int v = 1,int tl = 1,int tr = N){
        if(tl == tr){
            t[v] += val;
        }else{
            int tm = (tl + tr) >> 1;
            if(pos <= tm) upd(pos,val,v+v,tl,tm);
            else upd(pos,val,v+v+1,tm+1,tr);
            t[v] = t[v + v] + t[v + v + 1];
        }
    }
    int get(int l,int r,int v = 1,int tl = 1,int tr = N){
        if(l > r || tl > r || l > tr) return 0;
        if(tl >= l && tr <= r) return t[v];
        int tm = (tl + tr) >> 1;
        return get(l,r,v+v,tl,tm) + get(l,r,v+v+1,tm+1,tr);
    }
}A,B;
int find(int val){
    int it = lower_bound(a.begin(),a.end(),val) - a.begin();
    return it + 1;
}
bool cmp(int i,int j){
    return (sm[i] > sm[j]);
}
bool cmp1(int i,int j){
    return (z[i] > z[j]);
}
bool cmp2(int i,int j){
    return (y[i] > y[j]);
}
bool cmp3(int i,int j){
    return (t[i] > t[j]);
}
void test(){
    A.build();
    B.build();
    cin >> n >> q;
    p.resize(n);
    iota(p.begin(),p.end(),1);
    qq.resize(q);
    iota(qq.begin(),qq.end(),1);
    for(int i = 1;i <= n;i++){
        cin >> s[i] >> t[i];
        sm[i] = s[i] + t[i];
        a.push_back(s[i]);
        a.push_back(t[i]);
        a.push_back(sm[i]);
    }
    for(int i = 1;i <= q;i++){
        cin >> x[i] >> y[i] >> z[i];
        X[i] = x[i];
        Y[i] = y[i];
        Z[i] = z[i];
        a.push_back(x[i]);
        a.push_back(y[i]);
        a.push_back(z[i]);
    }
    sort(a.begin(),a.end());
    for(int i = 1;i <= n;i++){
        s[i] = find(s[i]);t[i] = find(t[i]);sm[i] = find(sm[i]);
    }
    for(int i = 1;i <= q;i++){
        x[i] = find(x[i]);y[i] = find(y[i]);z[i] = find(z[i]);
    }
    sort(p.begin(),p.end(),cmp);
    sort(qq.begin(),qq.end(),cmp1);
    int it = 0;
    vector<pair<int,int>> f;
    vector<int> pos;
    for(int i:qq){
        if(X[i] + Y[i] >= Z[i]){
            pos.push_back(i);
            continue;
        }
        while(it < p.size() && sm[p[it]] >= z[i]){
            A.upd(s[p[it]],1);
            B.upd(t[p[it]],1);
            f.push_back({s[p[it]],t[p[it]]});
            it++;
        }
        int col = 0;
        res[i] = A.get(x[i],N) + B.get(y[i],N) - it;
    }
    A.build();
    it = 0;
    sort(p.begin(),p.end(),cmp3);
    sort(pos.begin(),pos.end(),cmp2);
    vector<int> all;
    for(auto i:pos){

        while(it < n && t[p[it]] >= y[i]){
            A.upd(s[p[it]],1);
            all.push_back(s[p[it]]);
            it++;
        }
        int col = 0;
        // for(auto j:all){
        //     if(j >= x[i]) col++;
        // }
        // res[i] = col;
        // cout << i << ' ' << res[i] << "x\n";
        res[i] = A.get(x[i],N);
    }
    for(int i = 1;i <= q;i++){
        cout << res[i] << '\n';
    }
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; i++)
    {
        test();
    }
}

Compilation message (stderr)

examination.cpp: In function 'void test()':
examination.cpp:91:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |         while(it < p.size() && sm[p[it]] >= z[i]){
      |               ~~~^~~~~~~~~~
examination.cpp:97:13: warning: unused variable 'col' [-Wunused-variable]
   97 |         int col = 0;
      |             ^~~
examination.cpp:112:13: warning: unused variable 'col' [-Wunused-variable]
  112 |         int col = 0;
      |             ^~~

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