oj.uz

답안 #220270

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
220270 2020-04-07T13:28:14 Z Haunted_Cpp Topovi (COCI15_topovi) C++17
120 / 120
 1154 ms 39672 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};
 
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;
  //current_column.resize(n + 1);
  //current_row.resize(n + 1);
  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

# 결과 실행 시간 메모리 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 138 ms 6392 KB Output is correct
7 Correct 98 ms 5368 KB Output is correct
8 Correct 75 ms 4472 KB Output is correct
9 Correct 76 ms 4600 KB Output is correct
10 Correct 90 ms 4836 KB Output is correct
11 Correct 1139 ms 39572 KB Output is correct
12 Correct 1154 ms 39416 KB Output is correct
13 Correct 1154 ms 39568 KB Output is correct
14 Correct 1132 ms 39672 KB Output is correct
15 Correct 1132 ms 39416 KB Output is correct
16 Correct 1144 ms 39520 KB Output is correct
17 Correct 1090 ms 39624 KB Output is correct
18 Correct 1108 ms 39416 KB Output is correct
19 Correct 1099 ms 39420 KB Output is correct
20 Correct 1119 ms 39544 KB Output is correct