oj.uz

Submission #126969

# Submission time Handle Problem Language Result Execution time Memory
126969 2019-07-08T17:14:57 Z MohamedAhmed04 Examination (JOI19_examination) C++14
20 / 100
 2105 ms 221312 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 123 ms 94328 KB Output is correct
2 Correct 122 ms 94264 KB Output is correct
3 Correct 128 ms 94328 KB Output is correct
4 Incorrect 125 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 1991 ms 176568 KB Output is correct
2 Correct 2009 ms 176584 KB Output is correct
3 Correct 1878 ms 176544 KB Output is correct
4 Correct 1468 ms 216176 KB Output is correct
5 Correct 1095 ms 177668 KB Output is correct
6 Correct 1278 ms 215528 KB Output is correct
7 Correct 1977 ms 177060 KB Output is correct
8 Correct 1667 ms 176896 KB Output is correct
9 Correct 1666 ms 177028 KB Output is correct
10 Correct 1012 ms 177388 KB Output is correct
11 Correct 1452 ms 221312 KB Output is correct
12 Correct 1840 ms 220368 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1991 ms 176568 KB Output is correct
2 Correct 2009 ms 176584 KB Output is correct
3 Correct 1878 ms 176544 KB Output is correct
4 Correct 1468 ms 216176 KB Output is correct
5 Correct 1095 ms 177668 KB Output is correct
6 Correct 1278 ms 215528 KB Output is correct
7 Correct 1977 ms 177060 KB Output is correct
8 Correct 1667 ms 176896 KB Output is correct
9 Correct 1666 ms 177028 KB Output is correct
10 Correct 1012 ms 177388 KB Output is correct
11 Correct 1452 ms 221312 KB Output is correct
12 Correct 1840 ms 220368 KB Output is correct
13 Incorrect 2105 ms 176596 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #4
0 / 57.0

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