oj.uz

Submission #1110954

# Submission time Handle Problem Language Result Execution time Memory
1110954 2024-11-11T05:58:57 Z jklepec Topovi (COCI15_topovi) C++11
6 / 120
 1008 ms 65536 KB 
#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,ll> col, row, calc, calr, cntx, cnty;
map<pair<int,int>,ll> mp;
ll cnt1 = 0, cnt2 = 0;
int main()
{

    ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
    ll 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 += 2;
        }
        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 - ( (n - cnt2) * row[0] + (n - cnt1) * col[0] ) << endl;
    }
    return 0;
}

Subtask #1
6.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Incorrect 1 ms 336 KB Output isn't correct
3 Incorrect 1 ms 336 KB Output isn't correct
4 Incorrect 1 ms 336 KB Output isn't correct
5 Incorrect 1 ms 336 KB Output isn't correct
6 Incorrect 114 ms 11728 KB Output isn't correct
7 Incorrect 90 ms 11104 KB Output isn't correct
8 Incorrect 70 ms 9032 KB Output isn't correct
9 Incorrect 70 ms 9488 KB Output isn't correct
10 Incorrect 80 ms 9544 KB Output isn't correct
11 Runtime error 872 ms 65536 KB Execution killed with signal 9
12 Runtime error 1008 ms 65536 KB Execution killed with signal 9
13 Runtime error 865 ms 65536 KB Execution killed with signal 9
14 Runtime error 893 ms 65536 KB Execution killed with signal 9
15 Runtime error 858 ms 65536 KB Execution killed with signal 9
16 Runtime error 851 ms 65536 KB Execution killed with signal 9
17 Runtime error 804 ms 65536 KB Execution killed with signal 9
18 Runtime error 835 ms 65536 KB Execution killed with signal 9
19 Runtime error 941 ms 65536 KB Execution killed with signal 9
20 Runtime error 914 ms 65536 KB Execution killed with signal 9