Submission #361313

#	Time	Username	Problem	Language	Result	Execution time	Memory
361313		shahriarkhan	Examination (JOI19_examination)	C++14	100 / 100	1250 ms	55156 KiB

examination

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

const int mx = 2e5 + 5 ;

int ans[mx] , cnt_a , cnt_b , n , q ;

map<int,int> np , mp ;

set<int> A , B ;

struct BIT
{
    vector<int> t ;
    BIT(int n)
    {
        t = vector<int> (n + 5 , 0) ;
    }
    void update(int ind , int val)
    {
        while(ind<=mx)
        {
            t[ind] += val ;
            ind += (ind&(-ind)) ;
        }
    }
    int query(int l , int r)
    {
        --l ;
        int left = 0 , right = 0 ;
        while(l)
        {
            left += t[l] ;
            l -= (l&(-l)) ;
        }
        while(r)
        {
            right += t[r] ;
            r -= (r&(-r)) ;
        }
        return right - left ;
    }
} T(mx+5) ;

struct score
{
    int a , b , sum , type , idx ;
    score(int _a , int _b , int _sum , int _type , int _idx) : a(_a) , b(_b) , sum(_sum) , type(_type) , idx(_idx) {} ;

};

bool cmp1(const score &a , const score &b)
{
    if(a.sum==b.sum) return a.type < b.type ;
    return a.sum > b.sum ;
}

bool cmp2(const score &a , const score &b)
{
    if(a.a==b.a) return a.type < b.type ;
    return a.a > b.a ;
}

vector<score> scores ;

void divide(int l , int r)
{
    if(l==r) return ;
    int mid = (l+r)>>1 ;
    vector<score> tmp ;
    for(int i = l ; i <= mid ; ++i)
    {
        if(!scores[i].type) tmp.push_back(scores[i]) ;
    }
    for(int i = mid + 1 ; i <= r ; ++i)
    {
        if(scores[i].type) tmp.push_back(scores[i]) ;
    }
	sort(tmp.begin(),tmp.end() , cmp2) ;
    int siz = tmp.size() ;
    for(int i = 0 ; i < siz ; ++i)
    {
        if(!tmp[i].type) T.update(tmp[i].b,1) ;
        else ans[tmp[i].idx] += T.query(tmp[i].b,mx) ;
    }
    for(int i = 0 ; i < siz ; ++i)
    {
        if(!tmp[i].type) T.update(tmp[i].b,-1) ;
    }
    divide(l,mid) , divide(mid+1,r) ;
}

int main()
{
    scanf("%d%d",&n,&q) ;
    for(int i = 1 ; i <= n ; ++i)
    {
        int s , t ;
        scanf("%d%d",&s,&t) ;
        A.insert(s) , B.insert(t) ;
        scores.push_back(score(s,t,s+t,0,-1)) ;
    }
    for(int i = 1 ; i <= q ; ++i)
    {
        int x , y , z ;
        scanf("%d%d%d",&x,&y,&z) ;
        A.insert(x) , B.insert(y) ;
        scores.push_back(score(x,y,z,1,i)) ;
    }

    for(int i : A) np[i] = ++cnt_a ;
    for(int i : B) mp[i] = ++cnt_b ;

    for(int i = 0 ; i < (n+q) ; ++i)
    {
        scores[i].a = np[scores[i].a] , scores[i].b = mp[scores[i].b] ;
    }
    sort(scores.begin(),scores.end(),cmp1) ;
    divide(0,n+q-1) ;
    for(int i = 1 ; i <= q ; ++i) printf("%d\n",ans[i]) ;
    return 0 ;
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:95:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   95 |     scanf("%d%d",&n,&q) ;
      |     ~~~~~^~~~~~~~~~~~~~
examination.cpp:99:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   99 |         scanf("%d%d",&s,&t) ;
      |         ~~~~~^~~~~~~~~~~~~~
examination.cpp:106:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  106 |         scanf("%d%d%d",&x,&y,&z) ;
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

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