oj.uz

Submission #126952

# Submission time Handle Problem Language Result Execution time Memory
126952 2019-07-08T16:50:35 Z MohamedAhmed04 Examination (JOI19_examination) C++14
20 / 100
 1985 ms 223148 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];

vector<int>v ;
int n , q ;

void compress()
{
    sort(v.begin() , v.end()) ;
    unique(v.begin() , 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 ;
        was[x] = qa[i] ;
        was[y] = qb[i] ;
        was[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";
        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 = was[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 94300 KB Output is correct
2 Correct 125 ms 94356 KB Output is correct
3 Correct 125 ms 94252 KB Output is correct
4 Incorrect 125 ms 94416 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 1865 ms 171232 KB Output is correct
2 Correct 1838 ms 171524 KB Output is correct
3 Correct 1769 ms 171432 KB Output is correct
4 Correct 1220 ms 182772 KB Output is correct
5 Correct 1020 ms 166380 KB Output is correct
6 Correct 837 ms 167592 KB Output is correct
7 Correct 1780 ms 169740 KB Output is correct
8 Correct 1681 ms 169724 KB Output is correct
9 Correct 1552 ms 168124 KB Output is correct
10 Correct 886 ms 166060 KB Output is correct
11 Correct 1433 ms 223148 KB Output is correct
12 Correct 1858 ms 221292 KB Output is correct

Subtask #3
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1865 ms 171232 KB Output is correct
2 Correct 1838 ms 171524 KB Output is correct
3 Correct 1769 ms 171432 KB Output is correct
4 Correct 1220 ms 182772 KB Output is correct
5 Correct 1020 ms 166380 KB Output is correct
6 Correct 837 ms 167592 KB Output is correct
7 Correct 1780 ms 169740 KB Output is correct
8 Correct 1681 ms 169724 KB Output is correct
9 Correct 1552 ms 168124 KB Output is correct
10 Correct 886 ms 166060 KB Output is correct
11 Correct 1433 ms 223148 KB Output is correct
12 Correct 1858 ms 221292 KB Output is correct
13 Incorrect 1985 ms 177152 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 94300 KB Output is correct
2 Correct 125 ms 94356 KB Output is correct
3 Correct 125 ms 94252 KB Output is correct
4 Incorrect 125 ms 94416 KB Output isn't correct
5 Halted 0 ms 0 KB -