Submission #1138328

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138328		sussy	Pairs (IOI07_pairs)	C++20	100 / 100	956 ms	104772 KiB

pairs

#include <bits/stdc++.h>
using namespace std;
#define name "aaaaaa"
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using ppii = pair<ll, pii>;
using pll = pair<ll, ll>;
using ull = unsigned long long;

void file(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    if(fopen(name".inp", "r")) {
        freopen(name".inp", "r", stdin);
        freopen(name".out", "w", stdout);
    }
}

void type1(){
    int n, k;
    cin >> n >> k;
    int m; cin >> m;
    vector<int> v;
    for(int i = 1; i <= n; i++){
        int x; cin >> x;
        v.push_back(x);
    }
    sort(v.begin(), v.end());
    ll ans = 0;
    for(int i = 0; i < v.size(); i++){
        int pos = upper_bound(v.begin(), v.end(), v[i] + k) - v.begin() - 1;
        ans += pos - i;
    }
    cout << ans;
}

const int N = 6e5 + 5, M = 3e5, G = 6e5, L = 1e5, R = 5e5;

vector<int> pos[N];
vector<int> BIT[N];

void fakeAdd(int u, int v, int x){
    for(u; u <= G; u += u&(-u)){
        pos[u].push_back(v);
    }
}

void fakeQuery(int u, int v){
    for(u; u > 0; u -= u&(-u)){
        pos[u].push_back(v);
    }
}

void fakeQueryrect(int x1, int y1, int x2, int y2){
    fakeQuery(x2, y2);
    fakeQuery(x1 - 1, y2);
    fakeQuery(x2, y1 - 1);
    fakeQuery(x1 - 1, y1 - 1);
}

void compress(){
    for(int i = 1; i <= G; i++){
        pos[i].push_back(0);
        sort(pos[i].begin(), pos[i].end());
        pos[i].erase(unique(pos[i].begin(), pos[i].end()), pos[i].end());
        BIT[i].assign(pos[i].size(), 0);
    }
}

void add(int u, int v, int x){
    for(int i = u; i <= G; i += i&(-i)){
        for(int j = lower_bound(pos[i].begin(), pos[i].end(), v) - pos[i].begin(); j < BIT[i].size(); j += j&(-j)){
            BIT[i][j] += x;
        }
    }
}

int query(int u, int v){
    int sum = 0;
    for(int i = u; i > 0; i -= i&(-i)){
        for(int j = lower_bound(pos[i].begin(), pos[i].end(), v) - pos[i].begin(); j > 0; j -= j&(-j)){
            sum += BIT[i][j];
        }
    }
    return sum;
}

int queryrect(int x1, int y1, int x2, int y2){
    return query(x2, y2) - query(x1 - 1, y2) - query(x2, y1 - 1) + query(x1 - 1, y1 - 1);
}

pll a[N];

void type2(){
    ll n, d, m;
    cin >> n >> d >> m;
    for(int i = 1; i <= n; i++){
        cin >> a[i].first >> a[i].second;
        int x = a[i].first + a[i].second + M, y = a[i].first - a[i].second + M;
        a[i].first = x, a[i].second = y;
        fakeAdd(x, y, 1);
    }
    for(int i = 1; i <= n; i++){
        int x1 = a[i].first - d, y1 = a[i].second - d, x2 = a[i].first + d, y2 = a[i].second + d;
        // x1 = max(x1, L), y1 = max(y1, L), x2 = min(x2, R), y2 = min(y2, R);
        fakeQueryrect(x1, y1, x2, y2);
    }
    compress();

    for(int i = 1; i <= n; i++){
        add(a[i].first, a[i].second, 1);
    }
    ll ans = 0;
    for(int i = 1; i <= n; i++){
        int x1 = a[i].first - d, y1 = a[i].second - d, x2 = a[i].first + d, y2 = a[i].second + d;
        // x1 = max(x1, L), y1 = max(y1, L), x2 = min(x2, R), y2 = min(y2, R);
        ans += queryrect(x1, y1, x2, y2);
    }
    ans = (ans - n) / 2;
    cout << ans;
}

const int M3 = 230;

int ct[M3][M3][M3];

vector<pair<int, pii>> v;

int rect(int layer, int x1, int y1, int x2, int y2){
    x1 = max(x1, 1);
    x2 = min(x2, M3 - 1);
    y1 = max(y1, 1);
    y2 = min(y2, M3 - 1);
    return ct[layer][x2][y2] - ct[layer][x1 - 1][y2] - ct[layer][x2][y1 - 1] + ct[layer][x1 - 1][y1 - 1];
}

void type3(){
    int n, d, m;
    cin >> n >> d >> m;
    d = min(d, m * 3 - 1);
    for(int i = 1; i <= n; i++){
        int x, y, z;
        cin >> x >> y >> z;
        int y2 = y + z, z2 = y - z;
        y2 += 76, z2 += 76;
        ct[x][y2][z2]++;
        v.push_back({x, {y2, z2}});
    }
    for(int i = 1; i < M3; i++){
        for(int j = 1; j < M3; j++){
            for(int k = 1; k < M3; k++){
                ct[i][j][k] += ct[i][j - 1][k] + ct[i][j][k - 1] - ct[i][j - 1][k - 1];
            }
        }
    }
    ll ans = 0;
    for(auto i : v){
        int x = i.first, y = i.second.first, z = i.second.second;
        for(int j = d; j >= 0; j--){
            int layer = x - (d - j);
            if(layer < 0) break;
            int x1 = y - j, y1 = z - j, x2 = y + j, y2 = z + j;
            ans += rect(layer, x1, y1, x2, y2);
        }
        for(int j = d - 1; j >= 0; j--){
            int layer = x + (d - j);
            if(layer >= M3) break;
            int x1 = y - j, y1 = z - j, x2 = y + j, y2 = z + j;
            ans += rect(layer, x1, y1, x2, y2);
        }
    }
    ans = (ans - n) / 2;
    cout << ans;
}

void solve (){
    int b; cin >> b;
    if(b == 1){
        type1();
    }else if(b == 2){
        type2();
    }else{
        type3();
    }
}

int main(){
    // file();
    int test = 1;
    //cin >> test;
    while(test--){
        solve();
    }
}

Compilation message (stderr)

pairs.cpp: In function 'void file()':
pairs.cpp:14:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |         freopen(name".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
pairs.cpp:15:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |         freopen(name".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 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: 10 / 10
• Subtask 12: 10 / 10
• Subtask 13: 10 / 10