Submission #253224

#	Time	Username	Problem	Language	Result	Execution time	Memory
253224		Sprdalo	Topovi (COCI15_topovi)	C++17	120 / 120	411 ms	53220 KiB

topovi

#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);
}    

ll 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: 120 / 120