oj.uz

Submission #1088131

# Submission time Handle Problem Language Result Execution time Memory
1088131 2024-09-14T03:21:16 Z nguyen31hoang08minh2003 Topovi (COCI15_topovi) C++17
6 / 120
 182 ms 52904 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, N) {
        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
6.0 / 120.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Correct 1 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Incorrect 1 ms 348 KB Output isn't correct
5 Incorrect 0 ms 348 KB Output isn't correct
6 Runtime error 45 ms 18264 KB Execution killed with signal 11
7 Runtime error 44 ms 16052 KB Execution killed with signal 11
8 Runtime error 33 ms 13396 KB Execution killed with signal 11
9 Runtime error 36 ms 13664 KB Execution killed with signal 11
10 Runtime error 35 ms 14420 KB Execution killed with signal 11
11 Runtime error 149 ms 52672 KB Execution killed with signal 11
12 Runtime error 182 ms 52792 KB Execution killed with signal 11
13 Runtime error 140 ms 52816 KB Execution killed with signal 11
14 Runtime error 138 ms 52652 KB Execution killed with signal 11
15 Runtime error 143 ms 52816 KB Execution killed with signal 11
16 Runtime error 139 ms 52820 KB Execution killed with signal 11
17 Runtime error 146 ms 52812 KB Execution killed with signal 11
18 Runtime error 137 ms 52840 KB Execution killed with signal 11
19 Runtime error 134 ms 52716 KB Execution killed with signal 11
20 Runtime error 139 ms 52904 KB Execution killed with signal 11