Submission #98643

#	Time	Username	Problem	Language	Result	Execution time	Memory
98643		long10024070	Topovi (COCI15_topovi)	C++14	120 / 120	675 ms	22116 KiB

topovi

#define Link ""

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>

#define TASK "TOPOVI"

using namespace std;

const int maxn = 1e5 + 100;
int n,k,p,i[maxn],j[maxn],x[maxn],i1[maxn],j1[maxn],i2[maxn],j2[maxn],cnt;
map <int,int> pos;
int col[maxn*2],cntcol[maxn*2],row[maxn*2],cntrow[maxn*2];
long long res;
map <pair<int,int>,int> _x;

void Enter()
{
    cin >> n >> k >> p;
    for (int t=1;t<=k;++t)
        cin >> i[t] >> j[t] >> x[t];
    for (int t=1;t<=p;++t)
        cin >> i1[t] >> j1[t] >> i2[t] >> j2[t];
}

void Ranking(int a[], int b[], int c[])
{
    vector <int*> v;
    for (int i=1;i<=k;++i)
        v.push_back(&a[i]);
    for (int i=1;i<=p;++i)
        v.push_back(&b[i]);
    for (int i=1;i<=p;++i)
        v.push_back(&c[i]);
    sort(v.begin(),v.end(),
         [] (int *p, int *q)
         {
             return *p < *q;
         });
    int cnt = 0;
    int pre = -1;
    for (auto p : v) {
        if (*p != pre)
            ++cnt;
        pre = *p;
        *p = cnt;
    }
}

int Pos(int x)
{
    if (pos[x] == 0)
        pos[x] = ++cnt;
//    cout << cnt << '\n';
//    cout << x << ' ' << pos[x] << '\n';
    return pos[x];
}

void UpdateCol(int i, int x)
{
    --cntcol[Pos(col[i])];
    res += cntrow[Pos(col[i])];
//    cout << col[i] << '\n';
    col[i] ^= x;
//    cout << col[i] << '\n';
    ++cntcol[Pos(col[i])];
    res -= cntrow[Pos(col[i])];
}

void UpdateRow(int j, int x)
{
    --cntrow[Pos(row[j])];
    res += cntcol[Pos(row[j])];
//    cout << row[j] << '\n';
    row[j] ^= x;
//    cout << row[j] << '\n';
    ++cntrow[Pos(row[j])];
    res -= cntcol[Pos(row[j])];
}

void Update(int i, int j, int x)
{
    _x[{i,j}] ^= x;
    UpdateCol(i,x);
    UpdateRow(j,x);
//    cout << i << ' ' << j << ' ' << x << ' ' << res << '\n';
}

void Init()
{
    Ranking(i,i1,i2);
    Ranking(j,j1,j2);
    cntrow[Pos(0)] = n;
    cntcol[Pos(0)] = n;
    for (int t=1;t<=k;++t)
        Update(i[t],j[t],x[t]);
}

void Solve()
{
    for (int t=1;t<=p;++t) {
        int x = _x[{i1[t],j1[t]}];
        Update(i1[t],j1[t],x);
        Update(i2[t],j2[t],x);
        cout << res << '\n';
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

#ifdef LHL
    freopen(".INP","r",stdin);
    freopen(".OUT","w",stdout);
#else
//    freopen(TASK".INP","r",stdin);
//    freopen(TASK".OUT","w",stdout);
#endif // LHL

    Enter();
    Init();
    Solve();
}

• Subtask 1: 120 / 120