QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#602324#7031. Supreme Commanducup-team5071#TL 0ms3560kbC++207.0kb2024-09-30 22:56:092024-09-30 22:56:10

Judging History

你现在查看的是最新测评结果

  • [2024-09-30 22:56:10]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3560kb
  • [2024-09-30 22:56:09]
  • 提交

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
...

result: