oj.uz

Submission #253371

# Submission time Handle Problem Language Result Execution time Memory
253371 2020-07-27T19:07:43 Z Vimmer Topovi (COCI15_topovi) C++14
120 / 120
 786 ms 30840 KB 
#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("no-stack-protector")

#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define pf push_front
#define N 10005
#define M ll(998244353)
#define inf 1e9 + 1e9

using namespace std;
//using namespace __gnu_pbds;

typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef short int si;
typedef array <ll, 3> a3;
typedef array <ll, 4> a4;

//typedef tree <int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;


ll ans;

map <pair <ll, ll>, ll> a;

unordered_map <ll, ll> valx, valy, row, col;

set <ll> se, st;

void de(ll t, bool ob)
{
    if (ob) valx[row[t]]--; else valy[col[t]]--;
}

void ad(ll t, bool ob)
{
    if (ob) valx[row[t]]++; else  valy[col[t]]++;
}

int main()
{
    //freopen("input.txt", "r", stdin); //freopen("output4.txt", "w", stdout);

    ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    ll n, k, p;

    cin >> n >> k >> p;

    for (ll i = 0; i < k; i++)
    {
        ll x, y, val;

        cin >> x >> y >> val;

        row[x] ^= val;

        col[y] ^= val;

        a[{x, y}] = val;
    }

    valy[0] = valx[0] = n;

    for (auto it : col) {valy[0]--; valy[it.S]++;}

    for (auto it : row) {valx[0]--; valx[it.S]++;}

    for (auto it : valx) ans += it.S * valy[it.F];

    for (; p > 0; p--)
    {
        ll x1, x2, y1, y2;

        cin >> x1 >> y1 >> x2 >> y2;

        ll val = a[{x2, y2}] = a[{x1, y1}];

        se.clear();

        se.insert(row[x1]); se.insert(row[x2]); se.insert(col[y1]); se.insert(col[y2]);

        for (auto it : se) ans -= valx[it] * valy[it];

        de(x1, 1); de(x2, 1); de(y1, 0); de(y2, 0);

        row[x1] ^= val; col[y1] ^= val; row[x2] ^= val; col[y2] ^= val;

        st.clear();

        st.insert(row[x1]); st.insert(row[x2]); st.insert(col[y1]); st.insert(col[y2]);

        for (auto it : st) if (se.find(it) == se.end()) ans -= valx[it] * valy[it];

        ad(x1, 1); ad(x2, 1); ad(y1, 0); ad(y2, 0);

        for (auto it : se) ans += valx[it] * valy[it];

        for (auto it : st) if (se.find(it) == se.end()) ans += valx[it] * valy[it];

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

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 63 ms 5336 KB Output is correct
7 Correct 46 ms 4904 KB Output is correct
8 Correct 37 ms 3736 KB Output is correct
9 Correct 36 ms 3832 KB Output is correct
10 Correct 38 ms 3836 KB Output is correct
11 Correct 648 ms 30764 KB Output is correct
12 Correct 724 ms 30716 KB Output is correct
13 Correct 715 ms 30712 KB Output is correct
14 Correct 754 ms 30716 KB Output is correct
15 Correct 674 ms 30840 KB Output is correct
16 Correct 786 ms 30676 KB Output is correct
17 Correct 602 ms 30588 KB Output is correct
18 Correct 608 ms 30608 KB Output is correct
19 Correct 668 ms 30780 KB Output is correct
20 Correct 693 ms 30716 KB Output is correct