Submission #103276

#	Time	Username	Problem	Language	Result	Execution time	Memory
103276		pxh612	Examination (JOI19_examination)	C++14	100 / 100	1152 ms	54732 KiB

examination

#include<bits/stdc++.h>
using namespace std;

#define in ({ll x=0;int n=0,c=getchar();for(;!isdigit(c);c=getchar()) n=c=='-';for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
#define inchar ({char c=getchar();while(c==' '||c=='\n') c=getchar();c;})
#define DO for(bool __=1;__;___=0)

#define ll long long
#define FOR(i,a,b) for(int i(a);i<=b;i++)
#define ROF(i,a,b) for(int i(b);a<=i;i--)
#define rr(x) " "<<#x<<'='<<x<<" "

#define bit(x,i) ((x>>(i-1))&1ll)
#define on(x,i) (x|(1ll<<(i-1)))
#define off(x,i) (x&~(1ll<<(i-1)))
#define pow2(x) (1ll<<x)

#define mt make_tuple
#define pi pair<int,int>
#define x first
#define y second

#define VEC(i,a) for(auto&i:a)
#define pb push_back
#define allv(a) a.begin(),a.end()
#define endv(a) (int)a.size()-1
////////////////////////////////////////// NIRO
const int N=1e5+5;
int n,Q;

struct tp
{
    int a,b,c,id;
};
tp a[N],a2[N],q[N];
int don,ans[N],finda[N];

bool sortc(tp a,tp b){return a.c<b.c;}
bool sortab(tp u,tp v){return u.a<v.a||(u.a==v.a&&u.b<v.b);}



#define middle(a,b) (a+(b-a)/2)
#define Sfir 1,1,n
#define Snow S,l,r
#define Slef S*2,l,middle(l,r)
#define Srig S*2+1,middle(l,r)+1,r
int s[4*N];
vector<int> ffen[4*N],fen[4*N];
void BUI(int S,int l,int r)
{
   // cout<<rr(S) rr(l) rr(r) "\n";
    FOR(i,l,r) ffen[S].pb(a[i].b);
    sort(allv(ffen[S]));
    fen[S].resize(ffen[S].size(),0);

    //cout<<rr(S) ":";
    //VEC(i,ffen[S]) cout<<i<<" ";cout<<"\n";
    if(l==r) return;
    BUI(Slef);BUI(Srig);
}


void UPDFEN(int S,int v)
{
    //if(S==3&&v==70) cout<<"YES\n\n";
    int i=lower_bound(allv(ffen[S]),v)-ffen[S].begin()+1;
    for(;i>0;i-=i&-i) fen[S][i-1]++;
}
int GETFEN(int S,int v)
{
    int sum=0;
    int i=lower_bound(allv(ffen[S]),v)-ffen[S].begin()+1;
    for(;i<=fen[S].size();i+=i&-i) sum+=fen[S][i-1];
    //cout<<rr(S) rr(v) rr(i) rr(fen[S].size()) rr(sum) "\n";
    return sum;
}


void UPD(int S,int l,int r,int x)
{
    if(x<l||r<x) return;

    //if(S==1) cout<<"update" rr(S) rr(l) rr(r) rr(x) "\n";
    UPDFEN(S,a[x].b);
	if(l!=r)
        UPD(Slef,x),
        UPD(Srig,x);
}
int GET(int S,int l,int r,int u,int v,int z)
{
	if(v<l||r<u) return 0;

	if(u<=l&&r<=v) return GETFEN(S,z);
	return GET(Slef,u,v,z)+GET(Srig,u,v,z);
}

int FIND(int x)
{
    //cout<<"find" rr(x) " --> ";
    int l=1,r=n,res=0;

    while(l<=r)

    {
        int mid=l+(r-l)/2;
        if(x<=a[mid].a) res=mid,r=mid-1;
        else l=mid+1;
    }
    //cout<<rr(res) "\n";
    return res;
}

main()
{
    //freopen("nr.inp","r",stdin);
   // freopen("nr.out","w",stdout);
    n=in,Q=in;
    //cout<<rr(n) rr(Q) "\n";
    FOR(i,1,n)
    {
        int x=in,y=in;
        a[i]=a2[i]={x,y,x+y,i};
    }
    FOR(i,1,Q) q[i]={in,in,in,i};

    sort(a2+1,a2+n+1,sortc);
    sort(q+1,q+Q+1,sortc);
    sort(a+1,a+n+1,sortab);
    FOR(i,1,n) finda[a[i].id]=i;

    //FOR(i,1,n) cout<<rr(i) <<a[i].a<<" "<<a[i].b<<" "<<a[i].c<<"\n";
    //FOR(i,1,n) cout<<finda[i]<<" ";cout<<"\n";
    BUI(1,1,n);
    don=n;

    ROF(i,1,Q)
    {
        //cout<<"=======================" rr(i) rr(q[i].a) rr(q[i].b) rr(q[i].c) "\n";
        while(don>0&&q[i].c<=a2[don].c) UPD(Sfir,finda[a2[don].id]),don--;

        int findd=FIND(q[i].a);
        if(findd!=0) ans[q[i].id]=GET(Sfir,findd,n,q[i].b);
       // break;
    }
    FOR(i,1,Q) cout<<ans[i]<<"\n";
}

Compilation message (stderr)

examination.cpp: In function 'int GETFEN(int, int)':
examination.cpp:74:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(;i<=fen[S].size();i+=i&-i) sum+=fen[S][i-1];
          ~^~~~~~~~~~~~~~~
examination.cpp: At global scope:
examination.cpp:114:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^
examination.cpp: In function 'int main()':
examination.cpp:4:128: warning: narrowing conversion of '({...})' from 'long long int' to 'int' inside { } [-Wnarrowing]
 #define in ({ll x=0;int n=0,c=getchar();for(;!isdigit(c);c=getchar()) n=c=='-';for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
                                                                                                                                ^
examination.cpp:125:22: note: in expansion of macro 'in'
     FOR(i,1,Q) q[i]={in,in,in,i};
                      ^~
examination.cpp:4:128: warning: narrowing conversion of '({...})' from 'long long int' to 'int' inside { } [-Wnarrowing]
 #define in ({ll x=0;int n=0,c=getchar();for(;!isdigit(c);c=getchar()) n=c=='-';for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
                                                                                                                                ^
examination.cpp:125:25: note: in expansion of macro 'in'
     FOR(i,1,Q) q[i]={in,in,in,i};
                         ^~
examination.cpp:4:128: warning: narrowing conversion of '({...})' from 'long long int' to 'int' inside { } [-Wnarrowing]
 #define in ({ll x=0;int n=0,c=getchar();for(;!isdigit(c);c=getchar()) n=c=='-';for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
                                                                                                                                ^
examination.cpp:125:28: note: in expansion of macro 'in'
     FOR(i,1,Q) q[i]={in,in,in,i};
                            ^~

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