oj.uz

Submission #153946

# Submission time Handle Problem Language Result Execution time Memory
153946 2019-09-17T14:42:56 Z nicolaalexandra Topovi (COCI15_topovi) C++14
102 / 120
 2000 ms 39640 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
102.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 376 KB Output is correct
6 Correct 254 ms 6204 KB Output is correct
7 Correct 184 ms 5372 KB Output is correct
8 Correct 144 ms 4440 KB Output is correct
9 Correct 169 ms 4476 KB Output is correct
10 Correct 168 ms 4800 KB Output is correct
11 Execution timed out 2005 ms 39436 KB Time limit exceeded
12 Correct 1919 ms 39428 KB Output is correct
13 Correct 1991 ms 39428 KB Output is correct
14 Correct 1934 ms 39488 KB Output is correct
15 Correct 1938 ms 39440 KB Output is correct
16 Correct 1895 ms 39592 KB Output is correct
17 Correct 1943 ms 39564 KB Output is correct
18 Execution timed out 2045 ms 39496 KB Time limit exceeded
19 Execution timed out 2036 ms 39640 KB Time limit exceeded
20 Correct 1898 ms 39564 KB Output is correct