oj.uz

Submission #126965

# Submission time Handle Problem Language Result Execution time Memory
126965 2019-07-08T17:12:02 Z MohamedAhmed04 Examination (JOI19_examination) C++14
20 / 100
 2064 ms 222052 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 = 1e6 + 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<<was[qa[i]]<<" "<<was[qb[i]]<<" "<<was[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 ;
    for(int i = 0 ; i < q ; ++i)
    {
        while(idx < n && vp[idx].first >= vp2[i].first)
        {
            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 , N-1) - query(x-1 , N-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

# Verdict Execution time Memory Grader output
1 Correct 124 ms 94328 KB Output is correct
2 Correct 125 ms 94320 KB Output is correct
3 Correct 123 ms 94328 KB Output is correct
4 Incorrect 123 ms 94328 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1863 ms 169476 KB Output is correct
2 Correct 1897 ms 169296 KB Output is correct
3 Correct 1774 ms 169324 KB Output is correct
4 Correct 1179 ms 175592 KB Output is correct
5 Correct 1022 ms 165608 KB Output is correct
6 Correct 836 ms 166676 KB Output is correct
7 Correct 1853 ms 168436 KB Output is correct
8 Correct 1638 ms 168644 KB Output is correct
9 Correct 1682 ms 166548 KB Output is correct
10 Correct 858 ms 165228 KB Output is correct
11 Correct 1419 ms 222052 KB Output is correct
12 Correct 1857 ms 220252 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1863 ms 169476 KB Output is correct
2 Correct 1897 ms 169296 KB Output is correct
3 Correct 1774 ms 169324 KB Output is correct
4 Correct 1179 ms 175592 KB Output is correct
5 Correct 1022 ms 165608 KB Output is correct
6 Correct 836 ms 166676 KB Output is correct
7 Correct 1853 ms 168436 KB Output is correct
8 Correct 1638 ms 168644 KB Output is correct
9 Correct 1682 ms 166548 KB Output is correct
10 Correct 858 ms 165228 KB Output is correct
11 Correct 1419 ms 222052 KB Output is correct
12 Correct 1857 ms 220252 KB Output is correct
13 Incorrect 2064 ms 172568 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 94328 KB Output is correct
2 Correct 125 ms 94320 KB Output is correct
3 Correct 123 ms 94328 KB Output is correct
4 Incorrect 123 ms 94328 KB Output isn't correct
5 Halted 0 ms 0 KB -