Submission #401364


Source Code Expand

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <functional>
#include <iostream>
#include <iomanip>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <utility>
#include <vector>

using namespace std;

typedef long long Long;
#define Whole(xs) xs.begin(), xs.end()

template<class T>
ostream& operator<<(ostream& os, const vector<T>& vs) {
    if (vs.empty()) return os << "[]";
    os << "[" << vs[0];
    for (int i = 1; i < vs.size(); i++) os << " " << vs[i];
    return os << "]";
}

const int IINF = 1<<28;
const Long LINF = 1LL<<56;
#define INF IINF

struct P {
    int y, x;
    P(int y=0, int x=0) : y(y), x(x) {}
};

int R, C, K;
int N;
vector<P> F;
vector< vector<int> > sR;
void Input() {
    cin >> R >> C >> K;
    cin >> N;
    F.clear(); F.resize(N);
    sR.clear(); sR.resize(R);
    for (int i = 0; i < N; i++) {
        int y, x; cin >> y >> x;
        y--; x--;
        F[i].y = y;
        F[i].x = x;
        sR[y].push_back(x);
    }
}

struct S {
    int value, index;
    S(int v = 0, int i = 0) : value(v), index(i) {}
    bool operator<(const S& s) const {
        return value < s.value;
    }
};
ostream& operator<<(ostream& os, const S& s) {
    os << "(" << s.value << "," << s.index << ")";
    return os;
}

void Solve() {
    vector<int> cR(R, 0);
    vector<S> cC(C);
    for (int i = 0; i < C; i++) {
        cC[i].index = i;
    }
    for (int i = 0; i < N; i++) {
        int y = F[i].y,
            x = F[i].x;
        cR[y]++;
        cC[x].value++;
    }
    Long Ans = 0;
    for (int i = 0; i < N; i++) {
        int y = F[i].y,
            x = F[i].x;
        if (cR[y] + cC[x].value - 1 == K) {
            Ans++;
        }
    }
    sort(cC.begin(), cC.end());

    vector<int> rTable(C, 0);
    for (int i = 0; i < C; i++) {
        rTable[ cC[i].index ] = i;
    }

    //cerr << cR << endl;
    //cerr << cC << endl;
    //cerr << "INIT" << Ans << endl;
    for (int r = 0; r < R; r++) {
        int LB, UB;
        int k = K - cR[r];
        if (k < 0) continue;

        int lb = 0, ub = C;
        if (cC[lb].value >= k) {
            lb = ub = 0;
        } else {
            while (lb + 1 < ub) {
                int mid = (lb + ub) / 2;
                if (cC[mid].value < k) {
                    lb = mid;
                } else {
                    ub = mid;
                }
            }
        }
        LB = ub;
        lb = 0, ub = C;
        //cerr << k << " " << cC << endl;
        if (cC[ub - 1].value <= k) {
            ub = C;
        } else {
            while (lb + 1 < ub) {
                int mid = (lb + ub) / 2;
                if (cC[mid].value <= k) {
                    lb = mid;
                } else {
                    ub = mid;
                }
            }
        }
        UB = ub;
        //cerr << k << ", " << "(" << LB << ", " << UB << ")" << endl;

        for (int i = 0; i < sR[r].size(); i++) {
            int z = sR[r][i];
            if (LB <= rTable[z] && rTable[z] < UB) {
                Ans--;
            }
        }


        Ans += UB - LB;
    }
    cout << Ans << endl;
}

int main() {
    Input(); Solve();
    return 0;
}

Submission Info

Submission Time
Task C - 収集王
User izuru
Language C++ (GCC 4.9.2)
Score 100
Code Size 3427 Byte
Status AC
Exec Time 170 ms
Memory 7460 KB

Judge Result

Set Name Sample Subtask1 Subtask2
Score / Max Score 0 / 0 30 / 30 70 / 70
Status
AC × 3
AC × 18
AC × 33
Set Name Test Cases
Sample subtask0-sample01.txt, subtask0-sample02.txt, subtask0-sample03.txt
Subtask1 subtask0-sample01.txt, subtask0-sample02.txt, subtask0-sample03.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt
Subtask2 subtask0-sample01.txt, subtask0-sample02.txt, subtask0-sample03.txt, subtask1-01.txt, subtask1-02.txt, subtask1-03.txt, subtask1-04.txt, subtask1-05.txt, subtask1-06.txt, subtask1-07.txt, subtask1-08.txt, subtask1-09.txt, subtask1-10.txt, subtask1-11.txt, subtask1-12.txt, subtask1-13.txt, subtask1-14.txt, subtask1-15.txt, subtask2-01.txt, subtask2-02.txt, subtask2-03.txt, subtask2-04.txt, subtask2-05.txt, subtask2-06.txt, subtask2-07.txt, subtask2-08.txt, subtask2-09.txt, subtask2-10.txt, subtask2-11.txt, subtask2-12.txt, subtask2-13.txt, subtask2-14.txt, subtask2-15.txt
Case Name Status Exec Time Memory
subtask0-sample01.txt AC 29 ms 736 KB
subtask0-sample02.txt AC 25 ms 804 KB
subtask0-sample03.txt AC 26 ms 796 KB
subtask1-01.txt AC 26 ms 928 KB
subtask1-02.txt AC 26 ms 924 KB
subtask1-03.txt AC 26 ms 800 KB
subtask1-04.txt AC 26 ms 800 KB
subtask1-05.txt AC 26 ms 924 KB
subtask1-06.txt AC 26 ms 808 KB
subtask1-07.txt AC 26 ms 800 KB
subtask1-08.txt AC 26 ms 800 KB
subtask1-09.txt AC 25 ms 792 KB
subtask1-10.txt AC 26 ms 800 KB
subtask1-11.txt AC 26 ms 844 KB
subtask1-12.txt AC 26 ms 924 KB
subtask1-13.txt AC 26 ms 784 KB
subtask1-14.txt AC 26 ms 920 KB
subtask1-15.txt AC 26 ms 736 KB
subtask2-01.txt AC 27 ms 924 KB
subtask2-02.txt AC 28 ms 800 KB
subtask2-03.txt AC 53 ms 1320 KB
subtask2-04.txt AC 122 ms 3192 KB
subtask2-05.txt AC 126 ms 3356 KB
subtask2-06.txt AC 169 ms 7456 KB
subtask2-07.txt AC 106 ms 2344 KB
subtask2-08.txt AC 169 ms 7392 KB
subtask2-09.txt AC 169 ms 7452 KB
subtask2-10.txt AC 170 ms 7460 KB
subtask2-11.txt AC 164 ms 7408 KB
subtask2-12.txt AC 169 ms 7460 KB
subtask2-13.txt AC 165 ms 7400 KB
subtask2-14.txt AC 166 ms 7460 KB
subtask2-15.txt AC 169 ms 7460 KB