oj.uz

Submission #253223

# Submission time Handle Problem Language Result Execution time Memory
253223 2020-07-27T13:30:45 Z Sprdalo Topovi (COCI15_topovi) C++17
30 / 120
 400 ms 58964 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pi> vp;
typedef vector<pl> vpl;

unordered_map<int, int> r, c, tr, tc;

struct HASH{
  size_t operator()(const pair<int,int>&x)const{
    return hash<long long>()(((long long)x.first)^(((long long)x.second)<<32));
  }
};

unordered_map<pi, int, HASH> mapa;
void fast(){
    mapa.reserve(131072);
    mapa.max_load_factor(0.25);
    r.reserve(131072);
    r.max_load_factor(0.25);
    c.reserve(131072);
    c.max_load_factor(0.25);

    tr.reserve(131072);
    tr.max_load_factor(0.25);
    tc.reserve(131072);
    tc.max_load_factor(0.25);
}    

int sol, n;    

void dodaj(int x, int y, int z){
    sol -= n -  tc[r[x]];
    sol -= n - tr[c[y]];

    if (r[x] != c[y])
        ++sol;

    if (tr[r[x]])
        --tr[r[x]];
    r[x] ^= z;
    ++tr[r[x]];

    if (tc[c[y]])
        --tc[c[y]];
    c[y] ^= z;
    ++tc[c[y]];

    sol += n - tc[r[x]];
    sol += n - tr[c[y]];
    if (r[x] != c[y])
        --sol;

    mapa[{x, y}] ^= z;
}

signed main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); 
    cout.tie(nullptr); 
    cerr.tie(nullptr);    
    fast();

    int k, p;
    cin >> n >> k >> p;

    tr[0] = n;
    tc[0] = n;
    for (int i = 0; i < k; ++i){
        int x, y, z;
        cin >> x >> y >> z;
        dodaj(x, y, z);
    }

    for (int i = 0; i < p; ++i){
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        int z = mapa[{x1, y1}];
        dodaj(x1, y1, z);
        dodaj(x2, y2, z);

        cout << sol << '\n';
    }
}

Subtask #1
30.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5760 KB Output is correct
2 Correct 4 ms 5760 KB Output is correct
3 Correct 4 ms 5632 KB Output is correct
4 Correct 4 ms 5760 KB Output is correct
5 Correct 4 ms 5760 KB Output is correct
6 Incorrect 42 ms 9976 KB Output isn't correct
7 Incorrect 36 ms 9464 KB Output isn't correct
8 Incorrect 30 ms 8824 KB Output isn't correct
9 Incorrect 29 ms 8824 KB Output isn't correct
10 Incorrect 32 ms 9080 KB Output isn't correct
11 Incorrect 391 ms 58580 KB Output isn't correct
12 Incorrect 383 ms 58448 KB Output isn't correct
13 Incorrect 400 ms 58964 KB Output isn't correct
14 Incorrect 385 ms 58576 KB Output isn't correct
15 Incorrect 396 ms 58604 KB Output isn't correct
16 Incorrect 391 ms 58436 KB Output isn't correct
17 Incorrect 397 ms 58704 KB Output isn't correct
18 Incorrect 378 ms 58452 KB Output isn't correct
19 Incorrect 397 ms 58580 KB Output isn't correct
20 Incorrect 391 ms 58604 KB Output isn't correct