Submission #219622

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
219622	2020-04-05T19:18:27 Z	Haunted_Cpp	Topovi (COCI15_topovi)	C++17	120 / 120	1186 ms	39800 KB

topovi

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <cassert>
#include <string>
#include <cstring>
#include <bitset>
#include <random>
#include <chrono>
#include <iomanip>
 

#pragma GCC optimize ("Ofast")
#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")

 
#define FOR(i, a, b) for(int i = a; i < (int) b; i++)
#define F0R(i, a) FOR (i, 0, a)
#define ROF(i, a, b) for(int i = a; i >= (int) b; i--)
#define R0F(i, a) ROF(i, a, 0)
#define GO(i, a) for (auto i : a)
 
#define rsz resize
#define eb emplace_back
#define pb push_back
#define sz(x) (int) x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define f first
#define s second
 
using namespace std;
 
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vpii;
typedef vector<vi> vvi;
typedef vector<vpii> vvpii;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef vector<pi64> vpi64;
 
const int dr[] = {+1, -1, +0, +0, +1, -1, +1, -1};
const int dc[] = {+0, +0, +1, -1, +1, -1, -1, +1};
const int ms[] = {+31, +29, +31, 30, +31, +30, +31, +31, +30, +31, +30, +31};


map<int, int> current_row;
map<int, int> current_column;
map<int, int> linha_xor;
map<int, int> coluna_xor;
map<pii, int> torres;
 
int main () {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, t, q;
  cin >> n >> t >> q;
  i64 total = 1LL * n * n;
  linha_xor[0] = n;
  coluna_xor[0] = n;
  F0R (i, t) {
    int linha, coluna, valor;
    cin >> linha >> coluna >> valor;
    torres[{linha, coluna}] = valor;
    --linha_xor[current_row[linha]];
    current_row[linha] ^= valor;
    ++linha_xor[current_row[linha]];
    --coluna_xor[current_column[coluna]];
    current_column[coluna] ^= valor;
    ++coluna_xor[current_column[coluna]];
  } 
  
  i64 not_attacked = 0;
  GO (to, linha_xor) {
    int valor = to.f;
    int primeiro = to.s;
    int segundo = coluna_xor[valor];
    not_attacked += 1LL * primeiro * segundo;
  }
  
  while (q--) {
    int l1, c1, l2, c2;
    cin >> l1 >> c1 >> l2 >> c2;

    not_attacked -= coluna_xor[current_row[l1]];
    --linha_xor[current_row[l1]]; 
    
    not_attacked -= linha_xor[current_column[c1]];
    --coluna_xor[current_column[c1]];
    
    current_row[l1] ^= torres[{l1, c1}];
    current_column[c1] ^= torres[{l1, c1}];
    
    not_attacked += linha_xor[current_column[c1]];
    ++coluna_xor[current_column[c1]];
    
    not_attacked += coluna_xor[current_row[l1]];
    ++linha_xor[current_row[l1]];


    not_attacked -= coluna_xor[current_row[l2]];
    --linha_xor[current_row[l2]]; 
    
    not_attacked -= linha_xor[current_column[c2]];
    --coluna_xor[current_column[c2]];
    
    current_row[l2] ^= torres[{l1, c1}];
    current_column[c2] ^= torres[{l1, c1}];
    
    not_attacked += coluna_xor[current_row[l2]];
    ++linha_xor[current_row[l2]];
    not_attacked += linha_xor[current_column[c2]];
    ++coluna_xor[current_column[c2]];

    swap (torres[{l1, c1}], torres[{l2, c2}]);  
    
    cout << total - not_attacked  << '\n';
  }
  return 0;
}

Subtask #1

120.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	120 ms	6008 KB	Output is correct
7	Correct	91 ms	4856 KB	Output is correct
8	Correct	73 ms	4472 KB	Output is correct
9	Correct	74 ms	4600 KB	Output is correct
10	Correct	88 ms	4728 KB	Output is correct
11	Correct	1186 ms	39424 KB	Output is correct
12	Correct	1101 ms	39676 KB	Output is correct
13	Correct	1093 ms	39588 KB	Output is correct
14	Correct	1109 ms	39544 KB	Output is correct
15	Correct	1127 ms	39672 KB	Output is correct
16	Correct	1129 ms	39668 KB	Output is correct
17	Correct	1109 ms	39676 KB	Output is correct
18	Correct	1073 ms	39800 KB	Output is correct
19	Correct	1077 ms	39604 KB	Output is correct
20	Correct	1070 ms	39544 KB	Output is correct