oj.uz

Submission #153950

# Submission time Handle Problem Language Result Execution time Memory
153950 2019-09-17T14:49:38 Z nicolaalexandra Topovi (COCI15_topovi) C++14
84 / 120
 2000 ms 39712 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[make_pair(l1,c1)] = 0;
        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
84.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 360 KB Output is correct
6 Correct 234 ms 6048 KB Output is correct
7 Correct 181 ms 5396 KB Output is correct
8 Correct 143 ms 4344 KB Output is correct
9 Correct 146 ms 4472 KB Output is correct
10 Correct 197 ms 4688 KB Output is correct
11 Execution timed out 2055 ms 39372 KB Time limit exceeded
12 Execution timed out 2095 ms 39588 KB Time limit exceeded
13 Execution timed out 2015 ms 39456 KB Time limit exceeded
14 Correct 1962 ms 39704 KB Output is correct
15 Execution timed out 2020 ms 38956 KB Time limit exceeded
16 Execution timed out 2033 ms 39368 KB Time limit exceeded
17 Correct 1957 ms 39468 KB Output is correct
18 Execution timed out 2055 ms 39508 KB Time limit exceeded
19 Correct 1942 ms 39712 KB Output is correct
20 Correct 1956 ms 39520 KB Output is correct