AOJ1079 Cosmic Market
問題:
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1079
なんかimos法とかいろんなものがみえたが、問題文の制約をみて考え直す。
結局逆再生すればいいことに気付くだけの問題だった。後ろから見ると、一度たった人は立ちっぱなし、座った人は座りっぱなしということができることがわかる。
#include<stdio.h> #include<vector> #include<algorithm> using namespace std; int main() { for(;;) { int mx,my,query; scanf("%d%d%d",&mx,&my,&query); if(mx==0&&my==0&&query==0) { break; } vector<pair<pair<int,int>,int> >vec; for(int i=0;i<query;i++) { int za,zb,zc; scanf("%d%d%d",&za,&zb,&zc); vec.push_back(make_pair(make_pair(za,zb),zc)); } reverse(vec.begin(),vec.end()); vector<char>flx,fly; for(int j=0;j<mx;j++) { flx.push_back(0); } for(int k=0;k<my;k++) { fly.push_back(0); } int ux=0,uy=0; int sum=0; for(int l=0;l<query;l++) { if(vec[l].first.first==0) { if(flx[vec[l].first.second]==0) { ux++; if(vec[l].second==1) { sum+=my-uy; } flx[vec[l].first.second]=1; } } else { if(fly[vec[l].first.second]==0) { uy++; if(vec[l].second==1) { sum+=mx-ux; } fly[vec[l].first.second]=1; } } } printf("%d\n",sum); } }