oj.uz

Submission #98710

# Submission time Handle Problem Language Result Execution time Memory
98710 2019-02-25T08:17:18 Z Tieuphong Topovi (COCI15_topovi) C++11
120 / 120
 1989 ms 33784 KB 
/***************************************************************************/
/**********************  LANG TU HAO HOA  **********************************/
/***************************************************************************/
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define sz(x) ((int) x.size())
#define PB push_back
#define PF push_front
#define MP make_pair
#define ll long long
#define F first
#define S second
#define maxc 1000000007
#define MOD 1000000007
#define base 107
#define eps 1e-6
#define pi acos(-1)
#define N 100005
#define task ""
#define remain(x) ((x > MOD) ? (x - MOD) : x)

using namespace std;

int n, p, k;

ll res;

map <int, int> r, c, demC, demR;

map <pii, int> dd;

void Calc(int x, int y, int fl)
{
    res += fl * demC[r[x]];
    res += fl * demR[c[y]];
    if (r[x] == c[y]) res -= fl;
}

void Upd(int x, int y, int w)
{
    Calc(x, y, -1);
    demR[r[x]]--, demC[c[y]]--;
    r[x] ^= w, c[y] ^= w;
    demR[r[x]]++, demC[c[y]]++;
    Calc(x, y, 1);
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //freopen(task".inp", "r", stdin);
    //freopen(task".out", "w", stdout);
    cin >> n >> p >> k;
    res = 1ll*n*n;
    demR[0] = n;
    demC[0] = n;
    FOR(i, 1, p)
    {
        int u, v, w;
        cin >> u >> v >> w;
        Upd(u, v, w);
        dd[MP(u, v)] = w;
    }
    FOR(i, 1, k)
    {
        int x, y, u, v;
        cin >> x >> y >> u >> v;
        int w = dd[MP(x, y)];
        dd[MP(x, y)] = 0;
        dd[MP(u, v)] = w;
        Upd(x, y, w);
        Upd(u, v, w);
        cout << 1ll*n*n - res << '\n';
    }
    return 0;
}

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 183 ms 5372 KB Output is correct
7 Correct 133 ms 4728 KB Output is correct
8 Correct 146 ms 4088 KB Output is correct
9 Correct 133 ms 4088 KB Output is correct
10 Correct 139 ms 4268 KB Output is correct
11 Correct 1989 ms 33780 KB Output is correct
12 Correct 1785 ms 33588 KB Output is correct
13 Correct 1809 ms 33580 KB Output is correct
14 Correct 1694 ms 33608 KB Output is correct
15 Correct 1819 ms 33572 KB Output is correct
16 Correct 1781 ms 33504 KB Output is correct
17 Correct 1725 ms 33784 KB Output is correct
18 Correct 1858 ms 33592 KB Output is correct
19 Correct 1799 ms 33696 KB Output is correct
20 Correct 1815 ms 33728 KB Output is correct