oj.uz

Submission #165241

# Submission time Handle Problem Language Result Execution time Memory
165241 2019-11-26T08:27:14 Z egekabas Topovi (COCI15_topovi) C++14
120 / 120
 1788 ms 46056 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long   ll;
typedef unsigned long long   ull;
typedef long double ld;
typedef pair<ll, ll>    pll;
typedef pair<ull, ull>    pull;
typedef pair<ll, ll>  pii;
typedef pair<ld, ld>  pld;
ll n, k, p;
map<ll, ll> rowval;
map<ll, ll> colval;

map<ll, ll> valrow;
map<ll, ll> valcol;

map<pll, ll> rooks;
ll rowsize = 0;
ll colsize = 0;
ll overlap = 0;
void add(ll x, ll y, ll val){
    if(rowval[x] == 0)
        ++rowsize;
    else
        overlap -= valcol[rowval[x]];
    
    if(colval[y] == 0)
        ++colsize;
    else
        overlap -= valrow[colval[y]];

    if(rowval[x] == colval[y] && rowval[x] != 0 && colval[y] != 0)
        ++overlap;
    
    valrow[rowval[x]]--;
    rowval[x] ^= val;
    valrow[rowval[x]]++;

    valcol[colval[y]]--;
    colval[y] ^= val;
    valcol[colval[y]]++;

    if(rowval[x] == 0)
        --rowsize;
    else
        overlap += valcol[rowval[x]];
    
    if(colval[y] == 0)
        --colsize;
    else
        overlap += valrow[colval[y]];

    if(rowval[x] == colval[y] && rowval[x] != 0 && colval[y] != 0)
        --overlap;

}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    cin >> n >> k >> p;
    while(k--){
        ll t1, t2, t3;
        cin >> t1 >> t2 >> t3;
        rowval[t1] ^= t3;
        colval[t2] ^= t3;
        rooks[{t1, t2}] = t3;
    }

    for(auto u : colval){
        if(u.ss == 0)
            continue;
        ++colsize;
        valcol[u.ss]++;
    }
    for(auto u : rowval){
        if(u.ss == 0)
            continue;
        ++rowsize;
        valrow[u.ss]++;
    }
    for(auto u : valcol){
        overlap += u.ss*valrow[u.ff];
    }
    while(p--){
        ll t1, t2, t3, t4;
        cin >> t1 >> t2 >> t3 >> t4;
        add(t1, t2, rooks[{t1, t2}]);
        //cout << rowsize << " " << colsize << " " << overlap << " ";
        //cout << rowsize*n+colsize*n-rowsize*colsize-overlap << "\n";
        add(t3, t4, rooks[{t1, t2}]);
        rooks[{t3, t4}] = rooks[{t1, t2}];
        rooks[{t1, t2}] = 0;
        //cout << rowsize << " " << colsize << " " << overlap << " ";
        cout << rowsize*n+colsize*n-rowsize*colsize-overlap << "\n";
    }
}

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 190 ms 7104 KB Output is correct
7 Correct 136 ms 6264 KB Output is correct
8 Correct 107 ms 5112 KB Output is correct
9 Correct 110 ms 5368 KB Output is correct
10 Correct 138 ms 5496 KB Output is correct
11 Correct 1788 ms 45852 KB Output is correct
12 Correct 1556 ms 45896 KB Output is correct
13 Correct 1533 ms 45872 KB Output is correct
14 Correct 1545 ms 45764 KB Output is correct
15 Correct 1539 ms 45888 KB Output is correct
16 Correct 1548 ms 45852 KB Output is correct
17 Correct 1564 ms 46056 KB Output is correct
18 Correct 1541 ms 45760 KB Output is correct
19 Correct 1556 ms 45816 KB Output is correct
20 Correct 1523 ms 45988 KB Output is correct