oj.uz

Submission #644915

# Submission time Handle Problem Language Result Execution time Memory
644915 2022-09-25T13:32:56 Z BackNoob Topovi (COCI15_topovi) C++14
0 / 120
 1352 ms 41112 KB 
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define endl '\n'
#define MASK(i) (1LL << (i))
#define ull unsigned long long
#define ld long double
#define pb push_back
#define all(x) (x).begin() , (x).end()
#define BIT(x , i) ((x >> (i)) & 1)
#define TASK "task"
#define sz(s) (int) (s).size()
 
using namespace std;
const int mxN = 5e5 + 227;
const int inf = 1e9 + 277;
const int mod = 1e9 + 7;
const ll infll = 1e18 + 7;
const int base = 307;
const int LOG = 20;
 
template <typename T1, typename T2> bool minimize(T1 &a, T2 b) {
    if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b) {
    if (a < b) {a = b; return true;} return false;
}
 
struct item{
    int r1, c1, r2, c2;
} query[mxN];

int n;
int k;
int p;
map<int, int> row;
map<int, int> col;
map<int, int> cntrow;
map<int, int> cntcol;
map<pair<int, int>, int> val;
int timer = 0;
ll res = 0;
 


void del(int r, int c)
{
    if(row[r] == 0) res -= (n - sz(col));
    res -= cntcol[row[r]];

    if(col[c] == 0) res -= (n - sz(row));
    res -= cntrow[col[c]];

    if(row[r] == col[c]) ++res;

    cntrow[row[r]]--;
    cntcol[col[c]]--;
    row[r] ^= val[{r, c}];
    col[c] ^= val[{r, c}];
    cntrow[row[r]]++;
    cntcol[col[c]]++;
    val[{r, c}] = 0;

    if(row[r] == 0) res += (n - sz(col));
    res += cntcol[row[r]];

    if(col[c] == 0) res += (n - sz(row));
    res += cntrow[col[c]];

    if(row[r] == col[c]) --res;
}

void add(int r, int c)
{
    if(row[r] == 0) res -= (n - sz(col));
    res -= cntcol[row[r]];

    if(col[c] == 0) res -= (n - sz(row));
    res -= cntrow[col[c]];

    if(row[r] == col[c]) ++res;

    cntrow[row[r]]--;
    cntcol[col[c]]--;
    row[r] ^= val[{r, c}];
    col[c] ^= val[{r, c}];
    cntrow[row[r]]++;
    cntcol[col[c]]++;

    if(row[r] == 0) res += (n - sz(col));
    res += cntcol[row[r]];

    if(col[c] == 0) res += (n - sz(row));
    res += cntrow[col[c]];

    if(row[r] == col[c]) --res;
}    


void solve()
{
    cin >> n >> k >> p;

    for(int i = 1; i <= k; i++) {
        int r, c, x;
        cin >> r >> c >> x;
        row[r] ^= x;
        col[c] ^= x;
        val[{r, c}] = x;
    }

    for(int i = 1; i <= p; i++) {
        cin >> query[i].r1 >> query[i].c1 >> query[i].r2 >> query[i].c2;
        row[query[i].r1] ^= 0;
        row[query[i].r2] ^= 0;
        col[query[i].c1] ^= 0;
        col[query[i].c2] ^= 0;
    }

    res = 1LL * (n - sz(row)) * (n - sz(col));


    for(auto it : col) cntcol[it.se]++;
    for(auto it : row) cntrow[it.se]++;


    for(auto it : row) {
        if(it.se == 0) res += (n - sz(col));
        res += cntcol[it.se];
    }

    for(int i = 1; i <= p; i++) {
        int r1, c1, r2, c2;
        r1 = query[i].r1;
        c1 = query[i].c1;
        r2 = query[i].r2;
        c2 = query[i].c2;


        val[{r2, c2}] = val[{r1, c1}];
        del(r1, c1);
        add(r2, c2);
        cout << 1LL * n * n - res << endl;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

 
    int tc = 1;
    //cin >> tc;
    while(tc--) {
        solve();
    }
    return 0;
}

Subtask #1
0 / 120.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Incorrect 1 ms 340 KB Output isn't correct
4 Incorrect 1 ms 340 KB Output isn't correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Incorrect 142 ms 6352 KB Output isn't correct
7 Incorrect 97 ms 5452 KB Output isn't correct
8 Incorrect 79 ms 4488 KB Output isn't correct
9 Incorrect 80 ms 4592 KB Output isn't correct
10 Incorrect 108 ms 4940 KB Output isn't correct
11 Incorrect 1328 ms 41048 KB Output isn't correct
12 Incorrect 1332 ms 41112 KB Output isn't correct
13 Incorrect 1301 ms 40936 KB Output isn't correct
14 Incorrect 1352 ms 41016 KB Output isn't correct
15 Incorrect 1344 ms 41104 KB Output isn't correct
16 Incorrect 1339 ms 40956 KB Output isn't correct
17 Incorrect 1320 ms 40944 KB Output isn't correct
18 Incorrect 1315 ms 41012 KB Output isn't correct
19 Incorrect 1303 ms 40912 KB Output isn't correct
20 Incorrect 1316 ms 41068 KB Output isn't correct