2021“MINIEYE杯”中国大学生算法设计超级联赛 第九场题解

#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 1e5 + 7;
const int inf = 1e9 + 7;
typedef long long ll;
inline int max(int x,int y)
{return x > y ? x : y;}
inline int min(int x,int y)
{return x < y ? x : y;}
int Mincol[MAXN];
int Maxrow[MAXN];
/*
1
2 2 3
4 2
2 3
*/
int main()
{
//    freopen("input.txt","r",stdin);
//    freopen("ans.out","w",stdout);
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m;
        ll k;
        scanf("%d %d %lld",&n,&m,&k);
        memset(Mincol,0x3f,sizeof Mincol);
        memset(Maxrow,0,sizeof Maxrow);
        int ans = 0;
        if(k == 1)
        {
            for(int i = 1;i <= n;++i)
            for(int j = 1;j <= m;++j)
            {
                int x;
                scanf("%d",&x);
                if(i == 1)
                ans = max(ans,x);
            }
        }
        else
        {
            int fir = 0;
            for(int i = 1;i <= n;++i)
            for(int j = 1;j <= m;++j)
            {
                int x;
                scanf("%d",&x);
                if(i == 1 && j == 1)    fir = x;
                Mincol[j] = min(Mincol[j],x);
                
                Maxrow[i] = max(Maxrow[i],x);
            }
            if(k&1)
            {
                ans = inf;
                for(int i = 1;i <= n;++i)
                ans = min(ans,Maxrow[i]);
                
                ans = max(ans,fir);
            }
            else
            {
                ans = -inf;
                for(int i = 1;i <= m;++i)
                ans = max(ans,Mincol[i]);
                
                ans = max(ans,fir);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

#include <cstdio>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int MAXN = 5005;
int read()
{
    int x = 0,f = 1;
    char c = getchar();
    while(c > '9' || c < '0')    {if(c == '-')    f = -1;c = getchar();}
    while(c >= '0' && c <= '9')    {x = (x << 3) + (x << 1) + c - '0';c = getchar();}
    return x * f;
}
struct node{
    int dat;
    int idx;
}a[MAXN];
bool cmp(node a,node b)
{return a.dat > b.dat;}
int b[MAXN];
int ans[MAXN][2];
/*
1
3
1 1 1 
1 1 1
*/
unordered_map<int,int> mp[2];
bool cmp1(node a,node b)
{
    return a.idx < b.idx;
}
int main()
{
//    freopen("in.txt","r",stdin);
//    freopen("ans.out","w",stdout);
    int t = read();
    while(t--)
    {
        mp[0].clear();mp[1].clear();
        int n = read();
        for(int i = 1;i <= n;++i)    a[i].idx = i,a[i].dat = read();
        for(int i = 1;i <= n;++i)    b[i] = read();
        
        sort(a + 1,a + n + 1,cmp);
        for(int i = 1;i <= n;++i)
        {
            int le = i - 1,ri = 2;
            int now = a[i].dat + b[1];
            while(le >= 1 && ri <= n)
            {
                while(le >= 1 && ri <= n && a[le].dat + b[ri] > now)
                ++ri;
                if(ri > n)    break;
                --le,++ri;
                if(le < 1)    break;
            }
            ans[a[i].idx][0] = le + 1;
            if(mp[0].count(a[i].dat) == 0)    mp[0][a[i].dat] = le + 1;
            mp[0][a[i].dat] = min(mp[0][a[i].dat],le + 1);
            
            le = i + 1,ri = n - 1;
            now = a[i].dat + b[n];
            while(le <= n && ri >= 1)
            {
                while(le <= n && ri >= 1 && a[le].dat + b[ri] <= now)
                --ri;
                if(ri < 1)    break;
                ++le,--ri;
                if(le > n)    break;
            }
            ans[a[i].idx][1] = le - 1;
            if(mp[1].count(a[i].dat) == 0)    mp[1][a[i].dat] = le - 1;
            mp[1][a[i].dat] = min(mp[1][a[i].dat],le - 1);
        }
        sort(a + 1,a + n + 1,cmp1);
        for(int i = 1;i <= n;++i)
        printf("%d %d\n",mp[0][a[i].dat],mp[1][a[i].dat]);
    }
    return 0;
}