oj.uz

Submission #1088137

# Submission time Handle Problem Language Result Execution time Memory
1088137 2024-09-14T03:26:33 Z nguyen31hoang08minh2003 Topovi (COCI15_topovi) C++17
120 / 120
 596 ms 56404 KB 
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <math.h>
#include <bitset>
#include <vector>
#include <string>
#include <cstdio>
#include <cctype>
#include <numeric>
#include <fstream>
#include <sstream>
#include <cstdlib>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <stdio.h>
#include <string.h>
#include <iterator>
#include <iostream>
#include <algorithm>
#include <strings.h>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#define fore(i, a, b) for (int i = (a), i##_last = (b); i < i##_last; ++i)
#define fort(i, a, b) for (int i = (a), i##_last = (b); i <= i##_last; ++i)
#define ford(i, a, b) for (int i = (a), i##_last = (b); i >= i##_last; --i)
#define fi first
#define se second
#define pb push_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using ld = long double;

template<class A, class B> bool maxi(A &a, const B &b) {return (a < b) ? (a = b, true):false;};
template<class A, class B> bool mini(A &a, const B &b) {return (a > b) ? (a = b, true):false;};

typedef unsigned long long ull;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;

constexpr int MAX_N = 1E9, MAX_K = 1E5, MAX_P = 1E5;

map<int, int> rows, columns, rowCount, columnCount;
int N, K, P, R[MAX_K], C[MAX_K], X[MAX_K];
map<int, map<int, int> > which;
ll zeros, area;

int getValue(const map<int, int> &f, const int key) {
    const map<int, int>::const_iterator element = f.find(key);
    if (element == f.cend())
        return 0;
    return element -> second;
}

signed main() {

    int R1, C1, R2, C2;

    #ifdef LOCAL
    freopen("input.INP", "r", stdin);
    #endif // LOCAL
    cin.tie(0) -> sync_with_stdio(0);
    cout.tie(0);

    cin >> N >> K >> P;

    fore(i, 0, K) {
        cin >> R[i] >> C[i] >> X[i];
        rows[R[i]] ^= X[i];
        columns[C[i]] ^= X[i];
        which[R[i]][C[i]] = i;
    }

    area = 1LL * N * N;

    rowCount[0] = columnCount[0] = N;

    for (const auto &[key, value] : rows) {
        if (value == 0)
            continue;
        --rowCount[0];
        ++rowCount[value];
    }

    for (const auto &[key, value] : columns) {
        if (value == 0)
            continue;
        --columnCount[0];
        ++columnCount[value];
    }

    for (const auto &[key, value] : rowCount)
        zeros += 1LL * value * getValue(columnCount, key);

    fore(_, 0, P) {
        cin >> R1 >> C1 >> R2 >> C2;

        const int   i   =   which[R1][C1];
        int &r1 =   rows[R1],
            &c1 =   columns[C1],
            &r2 =   rows[R2],
            &c2 =   columns[C2];

        /*

            "Remove" process

        */

        zeros -= getValue(columnCount, r1) + getValue(rowCount, c1);
        if (r1 == c1)
            ++zeros;

        --rowCount[r1];
        --columnCount[c1];

        r1 ^= X[i];
        c1 ^= X[i];

        ++rowCount[r1];
        ++columnCount[c1];
        zeros += getValue(columnCount, r1) + getValue(rowCount, c1);
        if (r1 == c1)
            --zeros;

        /*

            "Add" process

        */

        zeros -= getValue(columnCount, r2) + getValue(rowCount, c2);
        if (r2 == c2)
            ++zeros;

        --rowCount[r2];
        --columnCount[c2];

        r2 ^= X[i];
        c2 ^= X[i];

        ++rowCount[r2];
        ++columnCount[c2];
        zeros += getValue(columnCount, r2) + getValue(rowCount, c2);
        if (r2 == c2)
            --zeros;

        /*

            "Final" steps

        */

        R[i] = R2;
        C[i] = C2;
        which[R2][C2] = i;

        cout << area - zeros << '\n';
    }

    return 0;
}

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 46 ms 8504 KB Output is correct
7 Correct 42 ms 7632 KB Output is correct
8 Correct 39 ms 6352 KB Output is correct
9 Correct 30 ms 6580 KB Output is correct
10 Correct 33 ms 6740 KB Output is correct
11 Correct 512 ms 56140 KB Output is correct
12 Correct 494 ms 56404 KB Output is correct
13 Correct 525 ms 56288 KB Output is correct
14 Correct 507 ms 56312 KB Output is correct
15 Correct 552 ms 56388 KB Output is correct
16 Correct 576 ms 56148 KB Output is correct
17 Correct 583 ms 56348 KB Output is correct
18 Correct 596 ms 56256 KB Output is correct
19 Correct 559 ms 56324 KB Output is correct
20 Correct 578 ms 56280 KB Output is correct