oj.uz

Submission #371240

# Submission time Handle Problem Language Result Execution time Memory
371240 2021-02-26T09:15:05 Z Atill83 Topovi (COCI15_topovi) C++14
120 / 120
 567 ms 25292 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e9+7;
const int MAXN = (int) 3e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int n, k, p;
unordered_map<int, int> col, row, kc, kr;
map<pii, int> mp;

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

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    cin>>n>>k>>p;
    kc[0] = kr[0] = n;
    for(int i = 0; i < k; i++){
        int x, y, pow;
        cin>>x>>y>>pow;
        mp[{x, y}] = pow;
        kc[col[y]]--;
        kr[row[x]]--;
        col[y] = (col[y] ^ pow);
        row[x] = (row[x] ^ pow);

        kc[col[y]]++;
        kr[row[x]]++;
        
    }

    ll ans = 1LL * n * n;


    for(auto u: kc){
        ans -= 1LL * u.ss * kr[u.ff];
    }

    for(int i = 0; i < p; i++){
        int x1, y1, x2, y2;
        cin>>x1>>y1>>x2>>y2;
        auto u = mp.find({x1, y1});
        int pwer = (*u).ss;

        mp.erase(u);
        mp[{x2, y2}] = pwer;

        int degR = row[x1], degC = col[y1];
        ans += kc[degR];
        kr[degR]--;
        ans += kr[degC];
        kc[degC]--;

        row[x1] ^= pwer;
        col[y1] ^= pwer;
        ans -= kr[col[y1]];
        kc[col[y1]]++;
        ans -= kc[row[x1]];
        kr[row[x1]]++;

        degR = row[x2], degC = col[y2];

        ans += kc[degR];
        kr[degR]--;
        ans += kr[degC];
        kc[degC]--;

        row[x2] ^= pwer;
        col[y2] ^= pwer;
        ans -= kr[col[y2]];
        kc[col[y2]]++;
        ans -= kc[row[x2]];
        kr[row[x2]]++;

        cout<<ans<<endl;
    }



    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 48 ms 3692 KB Output is correct
7 Correct 37 ms 3692 KB Output is correct
8 Correct 30 ms 3180 KB Output is correct
9 Correct 32 ms 3180 KB Output is correct
10 Correct 35 ms 3180 KB Output is correct
11 Correct 550 ms 25000 KB Output is correct
12 Correct 555 ms 25208 KB Output is correct
13 Correct 553 ms 24956 KB Output is correct
14 Correct 548 ms 25092 KB Output is correct
15 Correct 567 ms 25080 KB Output is correct
16 Correct 555 ms 25048 KB Output is correct
17 Correct 562 ms 25080 KB Output is correct
18 Correct 555 ms 25084 KB Output is correct
19 Correct 561 ms 25292 KB Output is correct
20 Correct 552 ms 24956 KB Output is correct