Submission #874919

#	Time	Username	Problem	Language	Result	Execution time	Memory
874919		Requiem	Examination (JOI19_examination)	C++17	100 / 100	499 ms	26692 KiB

examination

#include<bits/stdc++.h>
//#define int long long
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define INF 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define all(a) a.begin(),a.end()
#define pi 3.14159265359
#define TASKNAME "examination"
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
typedef pair<ii,ii> iv;
const int MAXN = 100005;
const int block = 316;
const int MAXBLOCK = MAXN / block;
int n,q,x,start,b;
iv score[MAXN], original[MAXN];
int nxt[6*MAXN],prep[MAXN],rev[MAXN],answer[MAXN];
struct BIT{
    vector<int> roirachoa;
    vector<int> T;
    int sz=0;
    void init(int _sz){
        sz = _sz;
        T.resize(_sz+3,0);
    }
    void upd(int id,int x){
        for(int i=id;i>0;i-=i&(-i)){
            T[i] += x;
        }
    }
    int get(int id){
        int res = 0;
        for(int i=id;i<=sz;i+=i&(-i)){
            res += T[i];
        }
        return res;
    }
    int getval(int x){
        return lower_bound(all(roirachoa),x) - roirachoa.begin() + 1;
    }
};
BIT st[MAXBLOCK*4];
void push(int node,int l,int r,int pos,int x){
//    cout<<node<<' '<<l<<' '<<r<<' '<<pos<<' '<<x<<endl;
    st[node].roirachoa.pb(x);
    if (l==r) return;
    int mid = (l+r)>>1;
    if (pos<=mid) push(node<<1,l,mid,pos,x);
    else push(node<<1|1,mid+1,r,pos,x);
}
vector<int> listval;
vector<iv> query;

void update(int node,int l,int r,int pos,int x){
    st[node].upd(st[node].getval(x),1);
//    cout<<"UPD: "<<node<<' '<<l<<' '<<r<<' '<<x<<' '<<st[node].getval(x)<<endl;
    if (l==r) return;
    int mid = (l+r)>>1;
    if (pos <= mid){
        update(node<<1,l,mid,pos,x);
    }
    else update(node<<1|1,mid+1,r,pos,x);
}
int getrange(int node,int l,int r,int u,int v,int x){
    if (l>=u and r<=v){
//        cout<<"GET: "<<node<<' '<<l<<' '<<r<<' '<<x<<' '<<st[node].getval(x)<<endl;
        return st[node].get(st[node].getval(x));
    }
    if (l>v or r<u) return 0;
    int mid = (l+r)>>1;
    return getrange(node<<1,l,mid,u,v,x) + getrange(node<<1|1,mid+1,r,u,v,x);
}
main()
{
    fast;
    if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
    }
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>score[i].se.fi>>score[i].se.se;
        score[i].fi.se = score[i].se.fi + score[i].se.se;
        listval.pb(score[i].se.fi);
        listval.pb(score[i].se.se);
        listval.pb(score[i].fi.se);
    }
    sort(score+1,score+1+n,[](const iv &a,const iv &b){
         return a.se.fi < b.se.fi;
    });

    for(int i=1;i<=q;i++){
        int x,y,z;
        cin>>x>>y>>z;
        listval.pb(x);
        listval.pb(y);
        listval.pb(z);
        query.pb({{i,x},{y,z}});
    }
    sort(listval.begin(),listval.end());
    listval.erase(unique(listval.begin(),listval.end()),listval.end());
    for(int i=1;i<=max(q,n);i++){
        if (i<=n){
            score[i].se.fi = lower_bound(all(listval),score[i].se.fi) - listval.begin() + 1;
            score[i].se.se = lower_bound(all(listval),score[i].se.se) - listval.begin() + 1;
            score[i].fi.se = lower_bound(all(listval),score[i].fi.se) - listval.begin() + 1;
        }
        if (i<=q){
            query[i-1].se.fi = lower_bound(all(listval),query[i-1].se.fi) - listval.begin() + 1;
            query[i-1].se.se = lower_bound(all(listval),query[i-1].se.se) - listval.begin() + 1;
            query[i-1].fi.se = lower_bound(all(listval),query[i-1].fi.se) - listval.begin() + 1;
        }
    }
    for(int i=1;i<=n;i++){
        score[i].fi.fi = i;
        original[i] = score[i];
    }
    int ptr = 1;
    for(int i=1;i<=listval.size();i++){
        while(ptr <= n and original[ptr].se.fi < i){
            ptr++;
        }
        if (ptr<=n) nxt[i] = original[ptr].fi.fi;
        else nxt[i] = n+1;
    }
    sort(query.begin(),query.end(),[](const iv &a,const iv &b){
         return a.se.se > b.se.se;
    });
    sort(score+1,score+1+n,[](const iv &a,const iv &b){
         return a.fi.se > b.fi.se;
    });

//    for(int i=1;i<=n;i++){
//        cout<<score[i].fi.se<<' '<<score[i].se.fi<<' '<<score[i].se.se<<endl;
//    }
    for(int i=1;i<=n;i++){
        prep[i] = i / block;
        push(1,0,MAXBLOCK,prep[i],original[i].se.se);
    }
    for(int i=1;i<MAXBLOCK*4;i++){
        sort(all(st[i].roirachoa));
//        cout<<"NODE: "<<i<<endl;
//        for(auto x: st[i].roirachoa){
//            cout<<x<<' ';
//        }
//        cout<<endl;
        st[i].roirachoa.erase(unique(all(st[i].roirachoa)),st[i].roirachoa.end());
        st[i].init(sz(st[i].roirachoa));
    }

    ptr = 1;
    for(int i=0;i<query.size();i++){
        while(ptr <= n and score[ptr].fi.se >= query[i].se.se){
            int RealIndex = score[ptr].fi.fi;
            rev[RealIndex]++;
            int b = prep[RealIndex];
//            cout<<b<<' '<<score[ptr].se.se<<endl;

            update(1,0,MAXBLOCK,b,score[ptr].se.se);
            ptr++;
        }
        start = nxt[query[i].fi.se];
        b = prep[start];
//        cout<<"START: "<<start<<' '<<b<<endl;
        if (start > n) continue;
        for(int j=start;j<=n;j++){
            if (original[j].se.fi >= query[i].fi.se and
                original[j].se.se >= query[i].se.fi and
                original[j].fi.se >= query[i].se.se and
                rev[j] > 0){
                    answer[query[i].fi.fi]++;
            }
            if (prep[j] != prep[j+1]) {
                break;
            }
        }
        if (b+1 <= MAXBLOCK) answer[query[i].fi.fi] += getrange(1,0,MAXBLOCK,b+1,MAXBLOCK,query[i].se.fi);

    }
    for(int i=1;i<=q;i++){
        cout<<answer[i]<<endl;
    }
}

Compilation message (stderr)

examination.cpp:4: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    4 | #pragma GCC optimization ("O3")
      | 
examination.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("unroll-loops")
      | 
examination.cpp:87:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   87 | main()
      | ^~~~
examination.cpp: In function 'int main()':
examination.cpp:133:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  133 |     for(int i=1;i<=listval.size();i++){
      |                 ~^~~~~~~~~~~~~~~~
examination.cpp:166:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  166 |     for(int i=0;i<query.size();i++){
      |                 ~^~~~~~~~~~~~~
examination.cpp:91:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:92:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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