oj.uz

답안 #98643

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
98643 2019-02-25T02:29:22 Z long10024070 Topovi (COCI15_topovi) C++14
120 / 120
 675 ms 22116 KB 
#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

# 결과 실행 시간 메모리 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