Submission #98643

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
98643	2019-02-25T02:29:22 Z	long10024070	Topovi (COCI15_topovi)	C++14	120 / 120	675 ms	22116 KB

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.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	384 KB	Output is correct
2	Correct	3 ms	384 KB	Output is correct
3	Correct	3 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	65 ms	4048 KB	Output is correct
7	Correct	56 ms	3436 KB	Output is correct
8	Correct	41 ms	2896 KB	Output is correct
9	Correct	55 ms	2912 KB	Output is correct
10	Correct	49 ms	3224 KB	Output is correct
11	Correct	675 ms	22116 KB	Output is correct
12	Correct	591 ms	22012 KB	Output is correct
13	Correct	644 ms	21956 KB	Output is correct
14	Correct	589 ms	22052 KB	Output is correct
15	Correct	618 ms	22008 KB	Output is correct
16	Correct	567 ms	21968 KB	Output is correct
17	Correct	639 ms	21984 KB	Output is correct
18	Correct	611 ms	21932 KB	Output is correct
19	Correct	624 ms	21948 KB	Output is correct
20	Correct	607 ms	22036 KB	Output is correct