oj.uz

Submission #153956

# Submission time Handle Problem Language Result Execution time Memory
153956 2019-09-17T14:58:00 Z nicolaalexandra Topovi (COCI15_topovi) C++14
120 / 120
 1997 ms 32060 KB 
#include <iostream>
#include <set>
#include <map>
#define INF 2000000000
using namespace std;

int n,k,q,sol,l,c,val,l1,l2,c1,c2,i;

map <int,int> dp_l,dp_c,fr_l,fr_c;
map <pair<int,int>,int> value;
int main (){

    cin>>n>>k>>q;
    /// numar cate casute au valorea 0
    long long sol = 1LL*n*n;
    fr_l[0] = n, fr_c[0] = n;
    for (i=1;i<=k;i++){
        cin>>l>>c>>val;
        int val_lin = dp_l[l], val_col = dp_c[c];

        sol -= fr_l[val_col];
        sol -= fr_c[val_lin];

        fr_l[val_lin]--, fr_c[val_col]--;
        dp_l[l] ^= val, dp_c[c] ^= val;
        val_lin = dp_l[l], val_col = dp_c[c];
        fr_l[val_lin]++, fr_c[val_col]++; /// tin minte frecv pt linii si coloane


        sol += fr_l[val_col];
        sol += fr_c[val_lin];

        value[make_pair(l,c)] = val;
    }

    for (;q--;){
        cin>>l1>>c1>>l2>>c2;
        int val = value[make_pair(l1,c1)];
        /// sterg
        int val_lin = dp_l[l1], val_col = dp_c[c1];
        value.erase(make_pair(l1,c1));
        sol -= fr_l[val_col];
        sol -= fr_c[val_lin];

        fr_l[val_lin]--, fr_c[val_col]--;
        dp_l[l1] ^= val, dp_c[c1] ^= val;
        val_lin = dp_l[l1], val_col = dp_c[c1];
        fr_l[val_lin]++, fr_c[val_col]++;

        sol += fr_l[val_col];
        sol += fr_c[val_lin];

        /// adaug
        value[make_pair(l2,c2)] = val;
        val_lin = dp_l[l2], val_col = dp_c[c2];
        sol -= fr_l[val_col];
        sol -= fr_c[val_lin];

        fr_l[val_lin]--, fr_c[val_col]--;
        dp_l[l2] ^= val, dp_c[c2] ^= val;
        val_lin = dp_l[l2], val_col = dp_c[c2];
        fr_l[val_lin]++, fr_c[val_col]++;

        sol += fr_l[val_col];
        sol += fr_c[val_lin];

        cout<<1LL*n*n-sol<<"\n";
    }


    return 0;
}

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 256 KB Output is correct
4 Correct 3 ms 256 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 232 ms 4892 KB Output is correct
7 Correct 178 ms 4600 KB Output is correct
8 Correct 140 ms 3832 KB Output is correct
9 Correct 145 ms 3892 KB Output is correct
10 Correct 167 ms 3884 KB Output is correct
11 Correct 1862 ms 31892 KB Output is correct
12 Correct 1997 ms 31824 KB Output is correct
13 Correct 1893 ms 31680 KB Output is correct
14 Correct 1835 ms 31776 KB Output is correct
15 Correct 1840 ms 31812 KB Output is correct
16 Correct 1962 ms 32060 KB Output is correct
17 Correct 1955 ms 31964 KB Output is correct
18 Correct 1928 ms 31996 KB Output is correct
19 Correct 1869 ms 31920 KB Output is correct
20 Correct 1884 ms 31692 KB Output is correct