oj.uz

Submission #253337

# Submission time Handle Problem Language Result Execution time Memory
253337 2020-07-27T18:31:28 Z Vimmer Topovi (COCI15_topovi) C++14
12 / 120
 1172 ms 47588 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 kolx, koly, ans;

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

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

void del(ll t, bool ob)
{
    ans -= kolx * koly;

    if (ob)
    {
        rowk[t]--;

        if (rowk[t] == 0) kolx++;
    }
    else
    {
        colk[t]--;

        if (colk[t] == 0) koly++;
    }

    ans += kolx * koly;
}

void add(ll t, bool ob)
{
    ans -= kolx * koly;

    if (ob)
    {
        rowk[t]++;

        if (rowk[t] == 1) kolx--;
    }
    else
    {
        colk[t]++;

        if (colk[t] == 1) koly--;
    }

    ans += kolx * koly;
}

void de(ll t, bool ob)
{
    if (ob)
    {
        if (row[t] == 0) return;

        ans -= valy[row[t]];

        valx[row[t]]--;
    }
    else
    {
        if (col[t] == 0) return;

        ans -= valx[col[t]];

        valy[col[t]]--;
    }
}

void ad(ll t, bool ob)
{
    if (ob)
    {
        if (row[t] == 0) return;

        ans += valy[row[t]];

        valx[row[t]]++;
    }
    else
    {
        if (col[t] == 0) return;

        ans += valx[col[t]];

        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;

    kolx = n; koly = n; ans = n * n;

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

        cin >> x >> y >> val;

        row[x] ^= val;

        col[y] ^= val;

        add(x, 1);

        add(y, 0);

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

    for (auto it : colk) valy[col[it.F]]++;

    for (auto it : rowk)
    {
        valx[row[it.F]]++;

        ans += valy[row[it.F]];
    }

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

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

        del(x1, 1); del(y1, 0);

        add(x2, 1); add(y2, 0);

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

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

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

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

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

Subtask #1
12.0 / 120.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 Incorrect 1 ms 384 KB Output isn't correct
4 Incorrect 1 ms 384 KB Output isn't correct
5 Incorrect 1 ms 384 KB Output isn't correct
6 Incorrect 111 ms 8248 KB Output isn't correct
7 Incorrect 89 ms 7896 KB Output isn't correct
8 Incorrect 47 ms 5880 KB Output isn't correct
9 Incorrect 43 ms 5880 KB Output isn't correct
10 Incorrect 64 ms 6136 KB Output isn't correct
11 Incorrect 1068 ms 47440 KB Output isn't correct
12 Incorrect 1172 ms 47316 KB Output isn't correct
13 Correct 959 ms 47316 KB Output is correct
14 Incorrect 861 ms 47312 KB Output isn't correct
15 Incorrect 868 ms 47360 KB Output isn't correct
16 Incorrect 995 ms 47588 KB Output isn't correct
17 Incorrect 879 ms 47352 KB Output isn't correct
18 Incorrect 868 ms 47420 KB Output isn't correct
19 Incorrect 873 ms 47260 KB Output isn't correct
20 Correct 859 ms 47300 KB Output is correct