oj.uz

Submission #98622

# Submission time Handle Problem Language Result Execution time Memory
98622 2019-02-25T01:40:35 Z tieunhi Topovi (COCI15_topovi) C++14
120 / 120
 1825 ms 34808 KB 
#include <bits/stdc++.h>
#define FOR(i, u, v) for (int i = u; i <= v; i++)
#define FORD(i, v, u) for (int i = v; i >= u; i--)
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define PB push_back
#define N 100005
#define mod 1000000007
#define ll long long

using namespace std;

map<int, int> row, col, cntR, cntC;
map<pii, int> dd;
ll res;
int sz, n, numQ;

void update(int u, int v, int sign)
{
    res += sign*cntC[row[u]];
    res += sign*cntR[col[v]];
    if (row[u] == col[v]) res -= sign;
}
void upd(int u, int v, int w)
{
    update(u, v, -1);

    cntR[row[u]]--;
    cntC[col[v]]--;
    row[u] ^= w; col[v] ^= w;
    cntR[row[u]]++;
    cntC[col[v]]++;

    update(u, v, 1);

}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("INP.TXT", "r", stdin);
    cin >> sz >> n >> numQ;

    res = 1ll*sz*sz;
    cntR[0] = cntC[0] = sz;

    FOR(i, 1, n)
    {
        int u, v, w; cin >> u >> v >> w;
        upd(u, v, w);
        dd[mp(u, v)] = w;
    }
    //cout <<res<<'\n';
    while (numQ--)
    {
        int u, v, x, y; cin >> u >> v >> x >> y;
        int w = dd[mp(u, v)]; dd[mp(u, v)] = 0; dd[mp(x, y)] = w;
        upd(u, v, w);
        upd(x, y, w);
        cout <<1ll*sz*sz -res<<'\n';
    }


}

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 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 209 ms 6148 KB Output is correct
7 Correct 140 ms 5496 KB Output is correct
8 Correct 134 ms 4472 KB Output is correct
9 Correct 153 ms 4600 KB Output is correct
10 Correct 141 ms 4812 KB Output is correct
11 Correct 1779 ms 34520 KB Output is correct
12 Correct 1797 ms 34632 KB Output is correct
13 Correct 1729 ms 34708 KB Output is correct
14 Correct 1707 ms 34540 KB Output is correct
15 Correct 1699 ms 34660 KB Output is correct
16 Correct 1670 ms 34736 KB Output is correct
17 Correct 1698 ms 34776 KB Output is correct
18 Correct 1799 ms 34700 KB Output is correct
19 Correct 1733 ms 34680 KB Output is correct
20 Correct 1825 ms 34808 KB Output is correct