oj.uz

Submission #219480

# Submission time Handle Problem Language Result Execution time Memory
219480 2020-04-05T11:35:18 Z Haunted_Cpp Topovi (COCI15_topovi) C++17
18 / 120
 72 ms 63992 KB 
#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};
 
const int N = 2e6 + 6;
vi current_row (N);
vi current_column (N);
vi linha_xor (N);
vi coluna_xor (N);
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;
  FOR (i, 1, n + 1) {
    linha_xor[0]++;
    current_row[i] = 0;
    coluna_xor[0]++;
    current_row[i] = 0;
  }
  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;
  F0R (i, N) {
    int valor = i;
    int primeiro = linha_xor[valor];
    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
18.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 31744 KB Output is correct
2 Runtime error 57 ms 63864 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Correct 23 ms 31744 KB Output is correct
4 Correct 23 ms 31616 KB Output is correct
5 Runtime error 57 ms 63992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 71 ms 63968 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 65 ms 63992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 67 ms 63992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 66 ms 63992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 66 ms 63992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 70 ms 63992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 69 ms 63992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 67 ms 63992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 68 ms 63864 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 72 ms 63992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 67 ms 63992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 68 ms 63864 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 68 ms 63992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 71 ms 63992 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 69 ms 63992 KB Execution killed with signal 11 (could be triggered by violating memory limits)