Submission #1110957

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1110957	2024-11-11T06:03:46 Z	jklepec	Topovi (COCI15_topovi)	C++11	120 / 120	1204 ms	65536 KB

topovi

#include <bits/stdc++.h>
#include <fstream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define endl '\n'
#define pb push_back
#define INF 200000000000000000
#define fi first
#define se second
using namespace std;
double const EPS = 1e-14;
typedef long long ll;
const ll P = 10007;
const ll mod = 1e9 + 7;
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; // find_by_order, order_of_key
const int M = 1e5 + 5;
map<int,int> col, row, calc, calr, cntx, cnty;
map<pair<int,int>,int> mp;
ll cnt1 = 0, cnt2 = 0;
int main()
{
 
    ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
    int n, k, p; cin >> n >> k >> p;
    ll tot = 0;
    set<int> stx, sty;
    for(int i = 0; i < k; i++) {
        int x, y, val; cin >> x >> y >> val;
        stx.insert(x); sty.insert(y);
        mp[{x,y}] = val;
        if(cntx[x] == 0) {
            tot += (n - cnt2);
            cnt1++;
        }
        cntx[x]++;
        if(cnty[y] == 0) {
            tot += (n - cnt1);
            cnt2++;
        }
        cnty[y]++;
        calr[x] ^= val;
        calc[y] ^= val;
    }
    for(auto i : stx) {
        row[calr[i]]++;
    }
    for(auto i : sty) {
        col[calc[i]]++;
    }
    for(auto i : stx) {
        tot -= col[calr[i]];
    }
    while(p--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
      /*  cntx[x1]--;
        if(cntx[x1] == 0) {
            tot -= (n - cnt2);
            cnt1--;
        }
        cnty[y1]--;
        if(cnty[y1] == 0) {
            tot -= (n - cnt1);
            cnt2--;
        }
      //  cout << tot << 'P' << endl;*/
        tot += col[calr[x1]];
        tot += row[calc[y1]];
 
        row[calr[x1]]--;
        col[calc[y1]]--;
 
        calr[x1] ^= mp[{x1,y1}];
        calc[y1] ^= mp[{x1,y1}];
 
        row[calr[x1]]++;
        col[calc[y1]]++;
 
        tot -= col[calr[x1]];
        tot -= row[calc[y1]];
 
        bool ok1 = 0, ok2 = 0;
         if(cntx[x2] == 0) {
            tot += (n - cnt2);
            cnt1++;
        }
        else {
            ok1 = 1;
            tot += col[calr[x2]];
 
        }
        cntx[x2]++;
 
        if(cnty[y2] == 0) {
            tot += (n - cnt1);
            cnt2++;
        }
        else {
            ok2 = 1;
           tot += row[calc[y2]];
 
           col[calc[y2]]--;
        }
        if(ok1 == 1) row[calr[x2]]--;
 
        cnty[y2]++;
        calr[x2] ^= mp[{x1,y1}];
        calc[y2] ^= mp[{x1,y1}];
 
        row[calr[x2]]++;
        col[calc[y2]]++;
 
        tot -= row[calc[y2]];
        tot -= col[calr[x2]];
 
        if(calc[y2] == calr[x2] && ok1 == 0 && ok2 == 0) {
            tot += 1;
        }
        else if(calc[y2] == calr[x2] && ok1 == 1 && ok2 == 0) {
            tot++;
        }
        else if(calc[y2] == calr[x2] && ok1 == 0 && ok2 == 1) {
            tot++;
        }
       mp[{x2,y2}] = mp[{x1,y1}];
       mp[{x1,y1}] = 0;
       cout << tot - ( (ll) (n - cnt2) * row[0] + (ll) (n - cnt1) * col[0] ) << endl;
    }
    return 0;
}

Subtask #1

120.0 / 120.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	336 KB	Output is correct
2	Correct	1 ms	336 KB	Output is correct
3	Correct	1 ms	336 KB	Output is correct
4	Correct	1 ms	336 KB	Output is correct
5	Correct	1 ms	480 KB	Output is correct
6	Correct	105 ms	9288 KB	Output is correct
7	Correct	91 ms	8788 KB	Output is correct
8	Correct	74 ms	7240 KB	Output is correct
9	Correct	68 ms	7240 KB	Output is correct
10	Correct	77 ms	7496 KB	Output is correct
11	Correct	1012 ms	65536 KB	Output is correct
12	Correct	1032 ms	65536 KB	Output is correct
13	Correct	1094 ms	65536 KB	Output is correct
14	Correct	1056 ms	65536 KB	Output is correct
15	Correct	1040 ms	65536 KB	Output is correct
16	Correct	960 ms	65536 KB	Output is correct
17	Correct	1034 ms	65536 KB	Output is correct
18	Correct	1000 ms	65536 KB	Output is correct
19	Correct	1204 ms	65536 KB	Output is correct
20	Correct	1141 ms	65536 KB	Output is correct