oj.uz

답안 #126973

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
126973 2019-07-08T17:22:31 Z MohamedAhmed04 Examination (JOI19_examination) C++14
20 / 100
 2370 ms 321280 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<pair<int , pair<int , int> > , null_type, less<pair<int , pair<int , int> > >, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int N = 2e6 + 5;

ordered_set bit[N];

void update(int x, int y , int idx)
{
	for(int i = x; i < N; i += i & -i)
		bit[i].insert({y, {x , idx}});
}
int query(int x, int y)
{
	int ans = 0;
	for(int i = x; i > 0; i -= i & -i)
    {
        ans += bit[i].order_of_key({y+1, {0 , -1}});
    }
	return ans;
}
/*int query(int x , int y)
{
    int ans = 0 ;
    while(x > 0)
    {
        int y1 = y ;
        while(y1 > 0)
        {
            ans += bit[{x , y1}] ;
            y1 -= (y1 & -y1) ;
        }
        x -= (x & -x) ;
    }
    return ans ;
}*/

int a[N], b[N] , ans[N];
int qa[N] , qb[N] , qc[N] , was[N] , was2[N];

vector<int>v ;
int n , q ;

void compress()
{
    sort(v.begin() , v.end()) ;
    v.erase(unique(v.begin() , v.end()) , v.end()) ;
    for(int i = 0 ; i < n ; ++i)
    {
        int x = lower_bound(v.begin() , v.end() , a[i]) - v.begin() ;
        int y = lower_bound(v.begin() , v.end() , b[i]) - v.begin() ;
        x += 2 ;
        y += 2 ;
        was[x] = a[i] ;
        was[y] = b[i] ;
        a[i] = x ;
        b[i] = y ;
    }
    for(int i = 0 ; i < q ; ++i)
    {
        int x = lower_bound(v.begin() , v.end() , qa[i]) - v.begin() ;
        int y = lower_bound(v.begin() , v.end() , qb[i]) - v.begin() ;
        int z = lower_bound(v.begin() , v.end() , qc[i]) - v.begin() ;
        x += 2 ;
        y += 2 ;
        z += 4 ;
        was2[x] = qa[i] ;
        was2[y] = qb[i] ;
        was2[z] = qc[i] ;
        qa[i] = x ;
        qb[i] = y ;
        qc[i] = z ;
    }
    return ;
}

int main()
{
    scanf("%d %d" , &n, &q) ;
    vector< pair<int , int> >vp ;
    vector< pair<int , pair<int , pair<int , int> > > >vp2 ;
    for(int i = 0 ; i < n ; ++i)
    {
        cin>>a[i]>>b[i] ;
        a[i] += 2 ;
        b[i] += 2 ;
        v.push_back(a[i]) ;
        v.push_back(b[i]) ;
        //vp.push_back({a[i] , b[i]}) ;
    }
    for(int i = 0 ; i < q ; ++i)
    {
        int x , y , z ;
        cin>>x>>y>>z ;
        x += 2 ;
        y += 2 ;
        z += 4 ;
        qa[i] = x ;
        qb[i] = y ;
        qc[i] = z ;
        v.push_back(qa[i]) ;
        v.push_back(qb[i]) ;
        v.push_back(qc[i]) ;
        //vp2.push_back({x , {y , {z , i}}}) ;
        //cout<<query(N-1 , N-1 , z) - query(x-1 , N-1 , z) - query(N-1 , y-1 , z) + query(x-1 , y-1 , z)<<"\n";
    }
    compress() ;
    for(int i = 0 ; i < n ; ++i)
    {
        //cout<<was[a[i]]<<" "<<was[b[i]]<<"\n";
        //cout<<was[a[i]]<<" "<<was[b[i]]<<"\n";
        vp.push_back({a[i] , b[i]}) ;
    }
    //for(int i = 0 ; i < q ; ++i)
    //    cout<<was2[qa[i]]<<" "<<was2[qb[i]]<<" "<<was2[qc[i]]<<"\n";
    for(int i = 0 ; i < q ; ++i)
    {
        vp2.push_back({qa[i] , {qb[i] , {qc[i] , i}}}) ;
    }
    sort(vp.begin() , vp.end()) ;
    reverse(vp.begin() , vp.end()) ;
    sort(vp2.begin() , vp2.end()) ;
    reverse(vp2.begin() , vp2.end()) ;
    int idx = 0 ;
    const int N2 = 2e9+10 ;
    for(int i = 0 ; i < q ; ++i)
    {
        while(idx < n && vp[idx].first >= vp2[i].first)
        {
            //cout<<vp[idx].second<<" "<<was[vp[idx].first] + was[vp[idx].second]<<"\n";
            update(vp[idx].second , was[vp[idx].first] + was[vp[idx].second] , idx) ;
            idx++ ;
        }
        int idxx = vp2[i].second.second.second ;
        int x = vp2[i].second.first , y = was2[vp2[i].second.second.first] ;
        ans[idxx] = query(N-1 , N2-1) - query(x-1 , N2-1) - query(N-1 , y-1) + query(x-1 , y-1) ;
    }
    for(int i = 0 ; i < q ; ++i)
        cout<<ans[i]<<"\n";
    return 0 ;
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:83:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d" , &n, &q) ;
     ~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
0 / 2.0

# 결과 실행 시간 메모리 Grader output
1 Correct 245 ms 188280 KB Output is correct
2 Correct 245 ms 188280 KB Output is correct
3 Correct 243 ms 188252 KB Output is correct
4 Correct 245 ms 188292 KB Output is correct
5 Correct 251 ms 188408 KB Output is correct
6 Correct 245 ms 188232 KB Output is correct
7 Incorrect 278 ms 191352 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2126 ms 276888 KB Output is correct
2 Correct 2163 ms 276784 KB Output is correct
3 Correct 2077 ms 276968 KB Output is correct
4 Correct 1745 ms 316304 KB Output is correct
5 Correct 1267 ms 277744 KB Output is correct
6 Correct 1495 ms 315892 KB Output is correct
7 Correct 2111 ms 277116 KB Output is correct
8 Correct 1875 ms 277160 KB Output is correct
9 Correct 1781 ms 277428 KB Output is correct
10 Correct 1179 ms 277576 KB Output is correct
11 Correct 1609 ms 321280 KB Output is correct
12 Correct 2370 ms 320488 KB Output is correct

Subtask #3
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2126 ms 276888 KB Output is correct
2 Correct 2163 ms 276784 KB Output is correct
3 Correct 2077 ms 276968 KB Output is correct
4 Correct 1745 ms 316304 KB Output is correct
5 Correct 1267 ms 277744 KB Output is correct
6 Correct 1495 ms 315892 KB Output is correct
7 Correct 2111 ms 277116 KB Output is correct
8 Correct 1875 ms 277160 KB Output is correct
9 Correct 1781 ms 277428 KB Output is correct
10 Correct 1179 ms 277576 KB Output is correct
11 Correct 1609 ms 321280 KB Output is correct
12 Correct 2370 ms 320488 KB Output is correct
13 Incorrect 2272 ms 277156 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# 결과 실행 시간 메모리 Grader output
1 Correct 245 ms 188280 KB Output is correct
2 Correct 245 ms 188280 KB Output is correct
3 Correct 243 ms 188252 KB Output is correct
4 Correct 245 ms 188292 KB Output is correct
5 Correct 251 ms 188408 KB Output is correct
6 Correct 245 ms 188232 KB Output is correct
7 Incorrect 278 ms 191352 KB Output isn't correct
8 Halted 0 ms 0 KB -