제출 #855052

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
855052		Shreyan_Paliwal	Pairs (IOI07_pairs)	C++17	30 / 100	473 ms	216324 KiB

pairs

#include <bits/stdc++.h>
using namespace std;

template<typename T>
string tostr(const T& value) {
    ostringstream oss;
    oss << fixed << setprecision(7);
    oss << value;
    return oss.str();
}

template<typename... Args>
string fstr(const string& format, Args... args) {
    string result = format;
    size_t pos = 0;
    size_t argIndex = 0;

    auto replaceArg = [&](const auto& arg) {
        pos = result.find("{}", pos);
        if (pos != string::npos) {
            result.replace(pos, 2, tostr(arg));
            ++argIndex;
        }
    };

    (replaceArg(args), ...);

    return result;
}

#define int long long
const int INF = LLONG_MAX / 2 - INT_MAX;
const int INFmem = 0x3f3f3f3f'3f3f3f3f;
const int inf = INT_MAX / 2;
const int infmem = 0x3f3f3f3f;

const int maxn = 100005;
const int maxm1 = 75000000;
const int maxm2 = 75000 * 2;
const int maxm3 = 75;

// dynamic segment tree pointers point update and range query for sum
struct ND {
    int v; int L, R; ND *l, *r;
    ND(int v, int L, int R, ND* l, ND* r) : v(v), L(L), R(R), l(l), r(r) {}
    ND() : v(0), L(0), R(0), l(nullptr), r(nullptr) {}
    ~ND() { delete l; delete r; }
    ND* gl() {
        if (!l) {
            int m = (L + R) >> 1;
            l = new ND(v/(R-L+1)*(m-L+1), L, m, nullptr, nullptr);
        }
        return l;
    }
    ND* gr() {
        if (!r) {
            int m = (L + R) >> 1;
            r = new ND(v/(R-L+1)*(R-m), m+1, R, nullptr, nullptr);
        }
        return r;
    }
    void upd(int K, int V) {
        if (L == R) { v += V; return; }
        int m = (L + R) >> 1;
        if (K <= m) { gl()->upd(K, V); }
        else { gr()->upd(K, V); }
        v = gl()->v + gr()->v;
    }
    int qry(int K1, int K2) {
        if (K2 < L || R < K1) { return 0; }
        if (K1 <= L && R <= K2) { return v; }
        int m = (L + R) >> 1;
        return gl()->qry(K1, K2) + gr()->qry(K1, K2);
    }
};

// binary indexed tree OF NDs, 2d
struct BIT {
    ND bit[maxm2 + 1];
    void upd(int K1, int K2) {
        for ( ; K1 <= maxm2; K1 += K1 & -K1)
            bit[K1].upd(K2, 1);
    }
    int qry(int K11, int K12, int K21, int K22) {
        int ret = 0;
        for ( ; K12; K12 -= K12 & -K12)
            ret += bit[K12].qry(K21, K22);
        K11--;
        for ( ; K11; K11 -= K11 & -K11)
            ret -= bit[K11].qry(K21, K22);
        return ret;
    }
};

int b, n, d, m;
int ans = 0;

void solve() {
    cin >> b >> n >> d >> m;
    if (b == 1) {
        vector<int> pts(n);
        for (int i = 0; i < n; i++) 
            cin >> pts[i];

        ND root = ND(0, 0, maxm1, nullptr, nullptr);
        for (auto& i : pts) {
            ans += root.qry(max(0ll, i - d), min(maxm1, i + d));
            root.upd(i, 1);
        }

        cout << ans << endl;
    } else if (b == 2) {
        vector<pair<int,int>> pts(n);
        for (int i = 0; i < n; i++) 
            cin >> pts[i].first >> pts[i].second;

        BIT bit; for (int i = 0; i <= maxm2; i++) bit.bit[i] = ND(0, 0, maxm2, nullptr, nullptr);

        for (auto& i : pts) {
            int a = i.first + i.second, b = maxm2 + i.first - i.second;
            ans += bit.qry(max(0ll, a - d), min(maxm2, a + d), max(0ll, b - d), min(maxm2, b + d));
            bit.upd(a, b);
        }

        cout << ans << endl;
    } else if (b == 3) {
        vector<pair<int,pair<int,int>>> pts(n);
        for (int i = 0; i < n; i++) 
            cin >> pts[i].first >> pts[i].second.first >> pts[i].second.second;
    }
}

// #define LOCAL
// #define CODEFORCES
signed main() {
    #ifndef LOCAL
    cin.tie(nullptr) -> ios::sync_with_stdio(false);
    #endif
    #ifdef LOCAL
    freopen("main.in", "r", stdin);
    #endif
    int t; 
    #ifdef CODEFORCES
    cin >> t;
    #endif
    #ifndef CODEFORCES
    t=1;
    #endif
    for (int i = 1; i <= t; i++) {
        #ifdef LOCAL
        cout << fstr("----- Case {} -----", i) << endl;
        auto startTime = clock();
        #endif 
        solve();
        #ifdef LOCAL
        cout << fstr("RUNTIME: {}", (double)(clock() - startTime)/CLOCKS_PER_SEC) << endl;
        cout << fstr("----- END CASE {} -----", i) << endl;
        #endif
        #ifdef LOCAL
        #endif
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

pairs.cpp: In member function 'long long int ND::qry(long long int, long long int)':
pairs.cpp:72:13: warning: unused variable 'm' [-Wunused-variable]
   72 |         int m = (L + R) >> 1;
      |             ^

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