Submission #124625

#	Time	Username	Problem	Language	Result	Execution time	Memory
124625		mirbek01	Examination (JOI19_examination)	C++11	100 / 100	309 ms	10184 KiB

examination

# include <bits/stdc++.h>
 
using namespace std;
 
const int N = 2e5 + 3;
 
struct st{
    int x, y, z;
    int a, b, c;
}a[N], b[N];
 
int n, m, ans[N], fen[3][N];
vector <int> v1, v2, v3;
 
void upd(int tp, int r){
    for(; r < N; r |= r + 1)
        fen[tp][r] ++;
}
int get(int tp, int l){
    int ret = 0;
    for(; l > 0; l = (l & (l + 1)) - 1)
        ret += fen[tp][l];
    return ret;
}
 
int main(){
    scanf("%d %d", &n, &m);
 
    for(int i = 1; i <= n; i ++){
        scanf("%d %d", &a[i].a, &a[i].b);
        a[i].c = a[i].a + a[i].b;
        v1.push_back(a[i].a);
        v2.push_back(a[i].b);
        v3.push_back(a[i].c);
        a[i].x = i;
    }
 
    for(int i = 1; i <= m; i ++){
        scanf("%d %d %d", &b[i].x, &b[i].y, &b[i].z);
        b[i].z = max(b[i].z, b[i].x + b[i].y);
        v1.push_back(b[i].x);
        v2.push_back(b[i].y);
        v3.push_back(b[i].z);
    }
 
    sort(v1.begin(), v1.end());
    v1.resize(unique(v1.begin(), v1.end()) - v1.begin());
    sort(v2.begin(), v2.end());
    v2.resize(unique(v2.begin(), v2.end()) - v2.begin());
    sort(v3.begin(), v3.end());
    v3.resize(unique(v3.begin(), v3.end()) - v3.begin());
 
    for(int i = 1; i <= n; i ++){
        a[i].a = lower_bound(v1.begin(), v1.end(), a[i].a) - v1.begin() + 1;
        a[i].b = lower_bound(v2.begin(), v2.end(), a[i].b) - v2.begin() + 1;
        a[i].c = lower_bound(v3.begin(), v3.end(), a[i].c) - v3.begin() + 1;
    }
    for(int i = 1; i <= m; i ++){
        b[i].x = lower_bound(v1.begin(), v1.end(), b[i].x) - v1.begin() + 1;
        b[i].y = lower_bound(v2.begin(), v2.end(), b[i].y) - v2.begin() + 1;
        b[i].z = lower_bound(v3.begin(), v3.end(), b[i].z) - v3.begin() + 1;
        b[i].a = i;
    }
 
    sort(a + 1, a + n + 1, [](st a, st b){
                            return a.c > b.c;});
    sort(b + 1, b + m + 1, [](st a, st b){
                            return a.z > b.z;});
 
    int pt = 0;
 
    for(int i = 1; i <= m; i ++){
        while(pt + 1 <= n && a[pt + 1].c >= b[i].z){
            pt ++;
            upd(1, a[pt].a);
            upd(2, a[pt].b);
        }
        ans[ b[i].a ] = pt - get(1, b[i].x - 1) - get(2, b[i].y - 1);
    }
 
    for(int i = 1; i <= m; i ++)
        printf("%d\n", ans[i]);
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &m);
     ~~~~~^~~~~~~~~~~~~~~~~
examination.cpp:30:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d", &a[i].a, &a[i].b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &b[i].x, &b[i].y, &b[i].z);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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