oj.uz

Submission #98559

# Submission time Handle Problem Language Result Execution time Memory
98559 2019-02-24T09:52:32 Z polyfish Topovi (COCI15_topovi) C++14
120 / 120
 1724 ms 46072 KB 
//Pantyhose(black) + glasses = infinity

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

#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int64_t _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int64_t _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"

map<int64_t, int64_t> r, c, row, col;
map<pair<int64_t, int64_t>, int64_t> mp;

int64_t updRow(int64_t idx, int64_t v) {
    int64_t res = -col[r[idx]];
    --row[r[idx]];
    r[idx] ^= v;
    res += col[r[idx]];
    ++row[r[idx]];
    return res;
}

int64_t updCol(int64_t idx, int64_t v) {
    int64_t res = -row[c[idx]];
    --col[c[idx]];
    c[idx] ^= v;
//    debug(c[idx]);
    res += row[c[idx]];
    ++col[c[idx]];
    return res;
}

void solve() {
    int64_t n;
    int64_t k, nQueries;

    cin >> n >> k >> nQueries;

    row[0] = col[0] = n;
    int64_t res = n * n;

    for (int64_t i=1; i<=k; ++i) {
        int64_t x, y;
        cin >> x >> y;
        cin >> mp[{x, y}];

        res += updRow(x, mp[{x, y}]);
        res += updCol(y, mp[{x, y}]);
    }

    while (nQueries--) {
        int64_t x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        mp[{x2, y2}] = mp[{x1, y1}];

        res += updRow(x1, mp[{x1, y1}]);
        res += updCol(y1, mp[{x1, y1}]);

        res += updRow(x2, mp[{x2, y2}]);
        res += updCol(y2, mp[{x2, y2}]);

        mp[{x1, y1}] = 0;

        cout << n*n - res << '\n';
    }
}

int main() {
	#ifdef GLASSES_GIRL
		freopen(FILE_NAME".in", "r", stdin);
		//freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);
    solve();
}

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 4 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 175 ms 7032 KB Output is correct
7 Correct 140 ms 6264 KB Output is correct
8 Correct 135 ms 5112 KB Output is correct
9 Correct 114 ms 5380 KB Output is correct
10 Correct 125 ms 5596 KB Output is correct
11 Correct 1531 ms 45904 KB Output is correct
12 Correct 1617 ms 46044 KB Output is correct
13 Correct 1535 ms 46024 KB Output is correct
14 Correct 1553 ms 45948 KB Output is correct
15 Correct 1601 ms 46044 KB Output is correct
16 Correct 1551 ms 46008 KB Output is correct
17 Correct 1545 ms 45820 KB Output is correct
18 Correct 1706 ms 46072 KB Output is correct
19 Correct 1724 ms 45916 KB Output is correct
20 Correct 1580 ms 45944 KB Output is correct