Submission #1143087

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143087		eggx50000	Pairs (IOI07_pairs)	C++20	70 / 100	57 ms	9032 KiB

pairs

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int b, n, d, m, tree[1000099], p, t, arr[100099];
int noo[80][160][160];

void update(int i, int v){
    while(i <= 1000000){
        tree[i] += v;
        i += i & -i;
    }
}

int query(int a){
    int cnt = 0;
    while(a){
        cnt += tree[a];
        a -= a & -a;
    }
    return cnt;
}

struct Da{
    int x, y, z;
    bool operator <(const Da &a) const{
        return y < a.y;
    }
} mut[100099];

queue <Da> que;

int rect(int lv, int x1, int y1, int x2, int y2){
    if(x1 < 1) x1 = 1;
    if(y1 < 1) y1 = 1;
    if(x2 > 2 * m) x2 = 2 * m;
    if(y2 > 2 * m) y2 = 2 * m;
    return noo[lv][x2][y2] - noo[lv][x1 - 1][y2] - noo[lv][x2][y1 - 1] + noo[lv][x1 - 1][y1 - 1];
}

int main()
{
    scanf("%d %d %d %d", &b, &n, &d, &m);
    if(b == 1){
        for(int i = 1; i <= n; i ++){
            scanf("%d", arr + i);
        }
        sort(arr + 1, arr + n + 1);
        long long cnt = 0;
        for(int i = 2; i <= n; i ++){
            long long ind = lower_bound(arr + 1, arr + i, arr[i] - d) - arr;
            cnt += i - ind;
        }
        printf("%lld", cnt);
        return 0;
    }
    else if(b == 2){
        if(2 * m <= d){
            printf("%lld", (long long)(n) * (n - 1) / 2);
            return 0;
        }
        for(int i = 1; i <= n; i ++){
            scanf("%d %d", &p, &t);
            mut[i] = {p - t + 3 * m, p + t};
        }
        long long cnt = 0;
        sort(mut + 1, mut + n + 1);
        for(int i = 1; i <= n; i ++){
            while(que.size() && mut[i].y - que.front().y > d){
                update(que.front().x, -1);
                que.pop();
            }
            cnt += (long long) query(mut[i].x + d) - query(max(0, mut[i].x - d - 1));
            que.push(mut[i]);
            update(mut[i].x, 1);
        }
        printf("%lld", cnt);
    }
    else{
        for(int i = 1; i <= n; i ++){
            int x, y, z;
            scanf("%d %d %d", &mut[i].x, &mut[i].y, &mut[i].z);
        }
        for(int i = 1; i <= n; i ++) noo[mut[i].z][mut[i].x - mut[i].y + m][mut[i].x + mut[i].y] ++;
        for(int i = 1; i <= 2 * m; i ++){
            for(int j = 1; j <= 2 * m; j ++){
                for(int k = 1; k <= m; k ++){
                    noo[k][i][j] += noo[k][i - 1][j] + noo[k][i][j - 1] - noo[k][i - 1][j - 1];
                }
            }
        }
        int ret = 0, sr = 0;
        for(int i = 1; i <= n; i ++){
            for(int j = 1; j <= mut[i].z; j ++){
                int k = d - (mut[i].z - j);
                if(k < 0) continue;
                int vv = rect(j, mut[i].x - mut[i].y - k + m, mut[i].x + mut[i].y - k, mut[i].x - mut[i].y + k + m, mut[i].x + mut[i].y + k);
                if(j == mut[i].z) sr += vv - 1;
                else ret += vv;
            }
        }
        printf("%d", ret + sr / 2);
    }
    return 0;
}

Compilation message (stderr)

pairs.cpp: In function 'int main()':
pairs.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   44 |     scanf("%d %d %d %d", &b, &n, &d, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp:47:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   47 |             scanf("%d", arr + i);
      |             ~~~~~^~~~~~~~~~~~~~~
pairs.cpp:64:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |             scanf("%d %d", &p, &t);
      |             ~~~~~^~~~~~~~~~~~~~~~~
pairs.cpp:83:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   83 |             scanf("%d %d %d", &mut[i].x, &mut[i].y, &mut[i].z);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 6 / 6
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 10 / 10
• Subtask 11: 0 / 10
• Subtask 12: 0 / 10
• Subtask 13: 0 / 10