/// COCI 2015-2016 contest 1
/**Lucky Boy**/
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define maxc 1000000007
#define maxn 200005
#define maxm 500005
#define pii pair <int,int>
#define Task "TOPOVI"
template <typename T> inline void read(T &x){char c;bool nega=0;while((!isdigit(c=getchar()))&&(c!='-'));if(c=='-'){nega=1;c=getchar();}x=c-48;while(isdigit(c=getchar())) x=x*10+c-48;if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10);putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){putchar('-');x=-x;}writep(x);putchar(' ');}
template <typename T> inline void writeln(T x){write(x);putchar('\n');}
using namespace std;
int m,n,q,row[maxn],col[maxn],cntr[maxn],cntc[maxn],limc,limr;
pair <pii,int> a[maxn];
pair <pii,pii> qq[maxn];
vector <int> rr,cc;
map <pii,bool> dd;
long long ans;
void Add(int x,int y,int z)
{
ans -= (m - cntc[row[x]]);
ans -= (m - cntr[col[y]]);
--cntc[col[y]];
--cntr[row[x]];
row[x] ^= z;
col[y] ^= z;
++cntc[col[y]];
++cntr[row[x]];
ans += (m - cntc[row[x]]);
ans += (m - cntr[col[y]]);
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen(Task".inp", "r",stdin);
//freopen(Task".out", "w",stdout);
cin >> m >> n >> q;
FOR(i,1,n)
{
int x,y,z;
cin >> x >> y >> z;
a[i] = mp(mp(x,y),z);
rr.pb(x),cc.pb(y);
dd[mp(x,y)] = 1;
}
FOR(i,1,q)
{
int x,y,u,v;
cin >> x >> y >> u >> v;
qq[i] = mp(mp(x,y),mp(u,v));
rr.pb(x);
rr.pb(u);
cc.pb(y);
cc.pb(v);
if (!dd[mp(u,v)]) a[++n] = mp(mp(u,v),0);
}
sort(rr.begin(),rr.end());
rr.resize(unique(rr.begin(),rr.end()) - rr.begin());
sort(cc.begin(),cc.end());
cc.resize(unique(cc.begin(),cc.end()) - cc.begin());
sort(a+1,a+n+1);
limr = rr.size();
limc = cc.size();
cntc[0] = limc;
cntr[0] = limr;
FOR(i,1,n)
{
Add(a[i].F.F,a[i].F.S,a[i].S);
}
FOR(i,1,q)
{
int x,y,u,v;
x = qq[i].F.F,
y = qq[i].F.S,
u = qq[i].S.F,
v = qq[i].S.S;
int pos1 = lower_bound(a+1,a+n+1,mp(mp(x,y),0)) - a,
pos2 = lower_bound(a+1,a+n+1,mp(mp(u,v),0)) - a;
x = upper_bound(rr.begin(),rr.end(),x) - rr.begin();
u = upper_bound(rr.begin(),rr.end(),u) - rr.begin();
y = upper_bound(cc.begin(),cc.end(),y) - cc.begin();
v = upper_bound(cc.begin(),cc.end(),v) - cc.begin();
Add(x,y,a[pos1].S);
Add(u,v,a[pos1].S);
swap(a[pos1].S,a[pos2].S);
cout << ans << '\n';
}
return 0;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
3 ms |
384 KB |
Output isn't correct |
| 2 |
Runtime error |
5 ms |
640 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 4 |
Incorrect |
2 ms |
384 KB |
Output isn't correct |
| 5 |
Runtime error |
3 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 6 |
Runtime error |
52 ms |
6512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 7 |
Runtime error |
37 ms |
5616 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 8 |
Runtime error |
28 ms |
4736 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 9 |
Runtime error |
31 ms |
4720 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 10 |
Runtime error |
33 ms |
5104 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 11 |
Runtime error |
417 ms |
38396 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 12 |
Runtime error |
457 ms |
38232 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 13 |
Runtime error |
438 ms |
38228 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 14 |
Runtime error |
431 ms |
38280 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Runtime error |
441 ms |
38340 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 16 |
Runtime error |
436 ms |
38336 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 17 |
Runtime error |
427 ms |
38388 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 18 |
Runtime error |
415 ms |
38332 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 19 |
Runtime error |
462 ms |
38168 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 20 |
Runtime error |
479 ms |
38272 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
