oj.uz

답안 #219492

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
219492 2020-04-05T11:49:15 Z Haunted_Cpp Topovi (COCI15_topovi) C++17
30 / 120
 94 ms 32256 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 + 5;
vi current_row (N);
vi current_column (N);

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;
  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) {
    if (linha_xor.find(i) != linha_xor.end() && coluna_xor.find(i) != coluna_xor.end()) {
      
      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
30.0 / 120.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 16000 KB Output is correct
2 Correct 26 ms 16000 KB Output is correct
3 Correct 21 ms 16000 KB Output is correct
4 Correct 22 ms 16000 KB Output is correct
5 Correct 26 ms 16000 KB Output is correct
6 Incorrect 94 ms 18936 KB Output isn't correct
7 Incorrect 81 ms 17912 KB Output isn't correct
8 Incorrect 69 ms 18040 KB Output isn't correct
9 Incorrect 77 ms 18040 KB Output isn't correct
10 Incorrect 84 ms 18296 KB Output isn't correct
11 Runtime error 45 ms 32248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 45 ms 32248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 47 ms 32248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 45 ms 32248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 48 ms 32248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 46 ms 32248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 44 ms 32248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 43 ms 32248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 48 ms 32248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 43 ms 32256 KB Execution killed with signal 11 (could be triggered by violating memory limits)