oj.uz

Submission #95225

# Submission time Handle Problem Language Result Execution time Memory
95225 2019-01-28T17:46:37 Z zeyad49 Topovi (COCI15_topovi) C++17
120 / 120
 1617 ms 39820 KB 
#include <cstdio>
#include <iostream>
#include <map>
using namespace std;
map<int,int> rows,cols,cntRows,cntCols;

map <pair<int, int>, int> power;
 long long ans;
    int n;
 void update(int r,int c,int x) {
    // subtract all cols with xor !=original xor of row r
    int original;
    original=rows[r];
    int y=n-cntCols[original];

    ans-=y;
    // add all cols with xor != new xor of row r
    int newXor=original^x;
   rows[r]=newXor;
    int z=cols[c];
    cntCols[z^x]++;
    cntCols[z]--;

    y=n-cntCols[newXor];
    ans+=y;
    cntRows[original]--;
    // subtract all rows with xor!=original xor of column c
    original=z;

    y=n-1-cntRows[original];
    ans-=y;
    newXor=original^x;
    cols[c]=newXor;
    //add all rows with xor!=new xor
    y=n-1-cntRows[newXor];
    ans+=y;
    z=rows[r];
    cntRows[z]++;
     power[make_pair(r, c)] ^= x;
}

int main() {
    cin>>n;
    int k,p;
    cin>>k>>p;
    int r,c,x;
    cntRows[0]=n;
    cntCols[0]=n;
    while(k--){
        cin>>r>>c>>x;
        r--;
        c--;
        update(r,c, x);

    }



    while(p-->0) {
        int r1,c1,r2,c2;
        cin>>r1>>c1>>r2>>c2;
        r1--;
        c1--;
        r2--;
        c2--;


        int x=power[make_pair(r1, c1)];
        update(r1, c1, x);
        update(r2,c2,x);
       cout<<ans<<'\n';
    }


    return 0;
}

Subtask #1
120.0 / 120.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 150 ms 5496 KB Output is correct
7 Correct 115 ms 4840 KB Output is correct
8 Correct 89 ms 4088 KB Output is correct
9 Correct 91 ms 4088 KB Output is correct
10 Correct 123 ms 4444 KB Output is correct
11 Correct 1617 ms 39544 KB Output is correct
12 Correct 1571 ms 39608 KB Output is correct
13 Correct 1542 ms 39612 KB Output is correct
14 Correct 1341 ms 39544 KB Output is correct
15 Correct 1323 ms 39616 KB Output is correct
16 Correct 1480 ms 39540 KB Output is correct
17 Correct 1408 ms 39672 KB Output is correct
18 Correct 1443 ms 39672 KB Output is correct
19 Correct 1319 ms 39524 KB Output is correct
20 Correct 1314 ms 39820 KB Output is correct