제출 #961693

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
961693		tudor_costin	Topovi (COCI15_topovi)	C++11	120 / 120	696 ms	32716 KiB

topovi

#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct hash_pair
{
    template<class t1,class t2>
    int operator()(const pair<t1,t2> p) const
    {
        int h1=hash<t1>{}(p.first);
        int h2=hash<t2>{}(p.second);
        if(h1!=h2) return h1^h2;
        return h1;
    }
};
unordered_map<int,int> xor_col,xor_lin;
unordered_map<int,int> cnt_col,cnt_lin;
unordered_map<pair<int,int>,int,hash_pair> rooks;
void update(int l,int c,ll& sol,int n)
{
    sol=sol-n+cnt_col[xor_lin[l]];
    sol=sol-n+cnt_lin[xor_col[c]];
    if(xor_lin[l]^xor_col[c]) sol++;

    cnt_lin[xor_lin[l]]--;
    xor_lin[l]^=rooks[{l,c}];
    cnt_lin[xor_lin[l]]++;

    cnt_col[xor_col[c]]--;
    xor_col[c]^=rooks[{l,c}];
    cnt_col[xor_col[c]]++;

    sol=sol+n-cnt_col[xor_lin[l]];
    sol=sol+n-cnt_lin[xor_col[c]];
    if(xor_lin[l]^xor_col[c]) sol--;
    return;
}
signed main()
{
    int n,k,p;
    cin>>n>>k>>p;
    cnt_col[0]=n;
    cnt_lin[0]=n;
    ll sol=0;
    while(k--)
    {
        int l,c,x;
        cin>>l>>c>>x;
        rooks[{l,c}]=x;
        update(l,c,sol,n);
    }
    while(p--)
    {
        int r1,c1,r2,c2;
        cin>>r1>>c1>>r2>>c2;
        update(r1,c1,sol,n);
        rooks[{r2,c2}]=rooks[{r1,c1}];
        update(r2,c2,sol,n);
        rooks[{r1,c1}]=0;
        cout<<sol<<'\n';
    }
    return 0;
}

• Subtask 1: 120 / 120