| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1110956 |
2024-11-11T06:01:53 Z |
jklepec |
Topovi (COCI15_topovi) |
C++11 |
|
1069 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 += 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 - ( (n - cnt2) * row[0] + (n - cnt1) * col[0] ) << endl;
}
return 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 |
336 KB |
Output is correct |
| 6 |
Correct |
124 ms |
10976 KB |
Output is correct |
| 7 |
Correct |
83 ms |
10568 KB |
Output is correct |
| 8 |
Correct |
65 ms |
8520 KB |
Output is correct |
| 9 |
Correct |
67 ms |
8796 KB |
Output is correct |
| 10 |
Correct |
76 ms |
8780 KB |
Output is correct |
| 11 |
Runtime error |
852 ms |
65536 KB |
Execution killed with signal 9 |
| 12 |
Runtime error |
869 ms |
65536 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
960 ms |
65536 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
1069 ms |
65536 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
930 ms |
65536 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
877 ms |
65536 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
870 ms |
65536 KB |
Execution killed with signal 9 |
| 18 |
Runtime error |
864 ms |
65536 KB |
Execution killed with signal 9 |
| 19 |
Runtime error |
873 ms |
65536 KB |
Execution killed with signal 9 |
| 20 |
Runtime error |
933 ms |
65536 KB |
Execution killed with signal 9 |
