oj.uz

Submission #153943

# Submission time Handle Problem Language Result Execution time Memory
153943 2019-09-17T14:37:19 Z nicolaalexandra Topovi (COCI15_topovi) C++14
60 / 120
 2000 ms 38360 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;
        sol -= fr_l[dp_c[c]];
        sol -= fr_c[dp_l[l]];
    
        fr_l[dp_l[l]]--, fr_c[dp_c[c]]--;
        dp_l[l] ^= val, dp_c[c] ^= val;
        fr_l[dp_l[l]]++, fr_c[dp_c[c]]++; /// tin minte frecv pt linii si coloane


        sol += fr_l[dp_c[c]];
        sol += fr_c[dp_l[l]];
      
        value[make_pair(l,c)] = val;
    }

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

        sol += fr_l[dp_c[c1]];
        sol += fr_c[dp_l[l1]];
     
        /// adaug
        value[make_pair(l2,c2)] = val;
        sol -= fr_l[dp_c[c2]];
        sol -= fr_c[dp_l[l2]];
     
        fr_l[dp_l[l2]]--, fr_c[dp_c[c2]]--;
        dp_l[l2] ^= val, dp_c[c2] ^= val;
        fr_l[dp_l[l2]]++, fr_c[dp_c[c2]]++;

        sol += fr_l[dp_c[c2]];
        sol += fr_c[dp_l[l2]];
       
        cout<<1LL*n*n-sol<<"\n";
    }


    return 0;
}

Subtask #1
60.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 324 ms 6080 KB Output is correct
7 Correct 233 ms 5424 KB Output is correct
8 Correct 182 ms 4472 KB Output is correct
9 Correct 163 ms 4476 KB Output is correct
10 Correct 189 ms 4716 KB Output is correct
11 Execution timed out 2093 ms 38348 KB Time limit exceeded
12 Execution timed out 2045 ms 38156 KB Time limit exceeded
13 Execution timed out 2021 ms 37672 KB Time limit exceeded
14 Execution timed out 2016 ms 37384 KB Time limit exceeded
15 Execution timed out 2106 ms 38096 KB Time limit exceeded
16 Execution timed out 2009 ms 38128 KB Time limit exceeded
17 Execution timed out 2050 ms 38360 KB Time limit exceeded
18 Execution timed out 2063 ms 38268 KB Time limit exceeded
19 Execution timed out 2045 ms 37704 KB Time limit exceeded
20 Execution timed out 2036 ms 37892 KB Time limit exceeded