QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#602324 | #7031. Supreme Command | ucup-team5071# | TL | 0ms | 3560kb | C++20 | 7.0kb | 2024-09-30 22:56:09 | 2024-09-30 22:56:10 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const bool test=false;
void solve()
{
int n,q;
cin>>n>>q;
ll ans=0;
if(n==1){
int z;cin>>z>>z;
while(q--){
char c;cin>>c;
if(c=='!')cout<<"0\n";
else if(c=='?'){
int x;cin>>x;
cout<<"1 1\n";
}
else {
int x;cin>>x;
}
}
return;
}
vector<int> x(n+1),y(n+1);
vector<int> up(n+1),down(n+1),left(n+1),right(n+1);
vector<int> px(n+1);//the x of point on y
vector<int> py(n+1);//the y of point on x
int lu=0,ld=0,ru=0,rd=0;
int l1=1,l2=n,t1=1,t2=n;//actually bound
int x1=1,x2=n,y1=1,y2=n;//virtual bound
for(int i=1;i<=n;i++){
cin>>x[i]>>y[i];
py[x[i]]=y[i];
px[y[i]]=x[i];
if(x[i]==1&&y[i]==1)lu++;
else if(x[i]==1&&y[i]==n)ru++;
else if(x[i]==n&&y[i]==1)ld++;
else if(x[i]==n&&y[i]==n)rd++;
else if(x[i]==1)up[y[i]]++;
else if(x[i]==n)down[y[i]]++;
else if(y[i]==1)left[x[i]]++;
else if(y[i]==n)right[x[i]]++;
}
auto actual_point = [&](int x,int y){
return make_pair(x-x1+l1,y-y1+t1);
};
auto merge = [&](int &x,int y){//calcu ans when merge
ans+=(ll)x*y;
if(test){if(x>0&&y>0)cout<<"merge x="<<x<<" y="<<y<<endl;}
x+=y;
};
int tt=0;
while(q--){
if(test){
cout<<"-----------------------------------------------------------"<<endl;
cout<<"times = "<<++tt<<endl;
cout<<"lu="<<lu<<" ld="<<ld<<" ru="<<ru<<" rd="<<rd<<endl;
cout<<"x1="<<x1<<" x2="<<x2<<" y1="<<y1<<" y2="<<y2<<endl;
cout<<"l1="<<l1<<" l2="<<l2<<" t1="<<t1<<" t2="<<t2<<endl;
cout<<"left :";for(int i=1;i<=n;i++)cout<<left[i]<<" \n"[i==n];
cout<<"right :";for(int i=1;i<=n;i++)cout<<right[i]<<" \n"[i==n];
cout<<"up :";for(int i=1;i<=n;i++)cout<<up[i]<<" \n"[i==n];
cout<<"down :";for(int i=1;i<=n;i++)cout<<down[i]<<" \n"[i==n];
}
char c;cin>>c;
if(c=='!'){cout<<ans<<"\n";continue;}
if(c=='?'){
int i;cin>>i;
int ax,ay;
if(x[i]<=x1&&y[i]<=y1)tie(ax,ay)=actual_point(x1,y1);
else if(x[i]<=x1&&y[i]>=y2)tie(ax,ay)=actual_point(x1,y2);
else if(x[i]>=x2&&y[i]<=y1)tie(ax,ay)=actual_point(x2,y1);
else if(x[i]>=x2&&y[i]>=y2)tie(ax,ay)=actual_point(x2,y2);
else if(x[i]<=x1)tie(ax,ay)=actual_point(x1,y[i]);
else if(x[i]>=x2)tie(ax,ay)=actual_point(x2,y[i]);
else if(y[i]<=y1)tie(ax,ay)=actual_point(x[i],y1);
else if(y[i]>=y2)tie(ax,ay)=actual_point(x[i],y2);
else tie(ax,ay)=actual_point(x[i],y[i]);
cout<<ax<<" "<<ay<<"\n";
continue;
}
int k;cin>>k;
{//move the actual bound to the map bound
int d=0;
if(c=='L'){d=min(k,t1-1);k-=d;t1-=d;t2-=d;}
if(c=='R'){d=min(k,n-t2);k-=d;t1+=d;t2+=d;}
if(c=='U'){d=min(k,l1-1);k-=d;l1-=d;l1-=d;}
if(c=='D'){d=min(k,n-l2);k-=d;l2+=d;l2+=d;}
if(k==0)continue;
}
if((c=='L'||c=='R')&&y1==y2){//just line move
continue;
}
if((c=='U'||c=='D')&&x1==x2){//just line move
continue;
}
while(k--){
if(c=='L'){
if(y1+1<y2){//not merge
if(x1==x2){
merge(lu,up[y1+1]);
}
else{
if(x1<px[y1+1]&&px[y1+1]<x2){
merge(left[px[y1]+1],1);
}
merge(lu,up[y1+1]);
merge(ld,down[y1+1]);
}
}
else{//merge
if(x1==x2){
merge(lu,ru);
}
else{
merge(lu,ru);
merge(ld,rd);
for(int i=x1+1;i<x2;i++)merge(left[i],right[i]);
}
}
y1++;t2--;
}
if(c=='R'){
if(y1+1<y2){//not merge
if(x1==x2){
merge(ru,up[y2-1]);
}
else{
if(x1<px[y2-1]&&px[y2-1]<x2){
merge(right[px[y2-1]],1);
}
merge(ru,up[y2-1]);
merge(rd,down[y2-1]);
}
}
else{//merge
if(x1==x2){
merge(lu,ru);
}
else{
merge(lu,ru);
merge(ld,rd);
for(int i=x1+1;i<x2;i++)merge(left[i],right[i]);
}
}
y2--;t1++;
}
if(c=='U'){
if(x1+1<x2){//not merge
if(y1==y2){
merge(lu,left[x1+1]);
}
else{
if(y1<py[x1+1]&&py[x1+1]<y2){
merge(up[py[x1+1]],1);
}
merge(lu,left[x1+1]);
merge(ru,right[x1+1]);
}
}
else{//merge
if(y1==y2){
merge(lu,ld);
}
else{
merge(lu,ld);
merge(ru,rd);
for(int i=y1+1;i<y2;i++)merge(up[i],down[i]);
}
}
x1++;l2--;
}
if(c=='D'){
if(x1+1<x2){//not merge
if(y1==y2){
merge(ld,left[x2-1]);
}
else{
if(y1<py[x2-1]&&py[x2-1]<y2){
merge(down[py[x2-1]],1);
}
merge(ld,left[x2-1]);
merge(rd,right[x2-1]);
}
}
else{//merge
if(y1==y2){
merge(lu,ld);
}
else{
merge(lu,ld);
merge(ru,rd);
for(int i=y1+1;i<y2;i++)merge(up[i],down[i]);
}
}
x2--;l1++;
}
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;cin>>T;while(T--)solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3560kb
input:
1 4 9 3 4 2 1 4 2 1 3 L 2 ? 1 ? 2 R 1 ? 1 ? 3 ! U 3 !
output:
3 2 2 1 3 3 4 2 0 3
result:
ok 6 lines
Test #2:
score: -100
Time Limit Exceeded
input:
500 2000 2000 492 502 1394 1025 980 1484 1135 599 760 242 575 1393 833 341 1364 453 1692 1515 1303 7 1429 1519 887 86 205 1874 1483 1797 649 1677 1717 298 416 1673 1696 896 1998 1154 638 1725 667 96 1467 1788 1438 759 285 1987 1985 736 95 140 596 1076 1089 238 1212 247 1287 1705 891 1237 941 622 930...
output:
169 1229 0 1609 1081 0 614 1509 0 1416 1109 0 1581 1103 0 455 1193 0 1886 1713 0 801 187 0 109 81 0 1028 378 0 1666 276 0 521 1976 0 1371 639 0 388 1375 0 134 806 0 568 495 0 1806 1065 0 357 828 0 1213 790 0 727 1967 0 23 311 0 1451 391 0 145 898 0 81 1023 0 1069 754 0 653 1932 0 813 909 0 1945 255 ...