답안 #98727

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
98727 2019-02-25T12:32:01 Z luckyboy Topovi (COCI15_topovi) C++14
120 / 120
1697 ms 33756 KB
/// COCI 2015-2016 contest 1
/**Lucky Boy**/
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define maxc 1000000007
#define maxn 200005
#define maxm 500005
#define pii pair <int,int>
#define Task "TOPOVI"
template <typename T> inline void read(T &x){char c;bool nega=0;while((!isdigit(c=getchar()))&&(c!='-'));if(c=='-'){nega=1;c=getchar();}x=c-48;while(isdigit(c=getchar())) x=x*10+c-48;if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10);putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){putchar('-');x=-x;}writep(x);putchar(' ');}
template <typename T> inline void writeln(T x){write(x);putchar('\n');}
using namespace std;
int n,m,q;
map <int,int> row,col,cntr,cntc;
map <pii,int> a;
long long ans;
void Add(int x,int y,int z)
{
    ans -= (m - cntc[row[x]]);
    ans -= (m - cntr[col[y]]);
    --cntc[col[y]];
    --cntr[row[x]];
    row[x] ^= z;
    col[y] ^= z;
    ++cntc[col[y]];
    ++cntr[row[x]];
    ans += (m - cntc[row[x]]);
    ans += (m - cntr[col[y]]);
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    //freopen(Task".inp", "r",stdin);
    //freopen(Task".out", "w",stdout);
    cin >> m >> n >> q;
    cntc[0] = cntr[0] = m;
    FOR(i,1,n)
    {
        int x,y,z;
        cin >> x >> y >> z;
        a[mp(x,y)] = z;
        Add(x,y,z);
    }
    while (q--)
    {
        int x,y,u,v;
        cin >> x >> y >> u >> v;
        int z = a[mp(x,y)];
        Add(x,y,z);
        Add(u,v,z);
        swap(a[mp(x,y)],a[mp(u,v)]);
        cout << ans << '\n';
    }
    return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 2 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 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 191 ms 5368 KB Output is correct
7 Correct 133 ms 4728 KB Output is correct
8 Correct 97 ms 3964 KB Output is correct
9 Correct 119 ms 4048 KB Output is correct
10 Correct 116 ms 4216 KB Output is correct
11 Correct 1480 ms 33600 KB Output is correct
12 Correct 1634 ms 33652 KB Output is correct
13 Correct 1697 ms 33716 KB Output is correct
14 Correct 1662 ms 33756 KB Output is correct
15 Correct 1584 ms 33756 KB Output is correct
16 Correct 1495 ms 33624 KB Output is correct
17 Correct 1495 ms 33632 KB Output is correct
18 Correct 1564 ms 33528 KB Output is correct
19 Correct 1578 ms 33580 KB Output is correct
20 Correct 1679 ms 33656 KB Output is correct