Submission #330244

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;

#define dbg(x) cerr << (#x) << " --> " << (x) << endl
#define lli long long int
#define pii pair<int,int>
#define mod 1000000007
#define N (int)1e6+10
#define mp make_pair
#define pb push_back
#define nd second
#define st first
#define endl '\n'
#define inf mod
#define sag (sol|1)
#define sol (root<<1)
#define ort ((bas+son)>>1)

vector< pii > a1,a2;
int x,y,n,m,i,j,k;
int mn = 1000000,ans1,ans2;
int dp[5005][5005];
int H[5005][5005];
int sa[5005];
int su[5005];

bool cmp(pii x,pii y){
    if(x.nd < y.nd)
        return 1;
    return 0;
}

int main(){

    cin >> n >> m;

    for(i=1 ; i<=n ; i++){
        cin >> x >> y;
        a1.pb(mp(x,i));
        a2.pb(mp(y,i));
    }

    sort(a1.begin(),a1.end());
    sort(a2.begin(),a2.end());

    for(i=0 ; i<n ; i++){
        a1[i].st = i+1;
        a2[i].st = i+1;
    }

    sort(a1.begin(),a1.end(),cmp);
    sort(a2.begin(),a2.end(),cmp);

    for(i=0 ; i<n ; i++){
        sa[a1[i].st] = a2[i].st;
        su[a2[i].st] = a1[i].st;
        H[a1[i].st][a2[i].st] = 1;
    }

    for(i=1 ; i<=n ; i++)
        for(j=1 ; j<=n ; j++)
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + H[i][j];

    for(i=0 ; i<n ; i++)
        for(j=0 ; j<n ; j++){
            int x1 = a1[i].st; int y1 = a2[i].st;
            int x2 = a1[j].st; int y2 = a2[j].st;

            if(x1 < x2) swap(x1,x2);
            if(y1 < y2) swap(y1,y2);

            int t = dp[x1][y1] + dp[x2][y2] - dp[x1][y2-1] - dp[x2-1][y1] - 1 ;

            if(sa[x2] < y2) t--;
            if(su[y2] < x2) t--;

            if(t>=m and mn>t){
                mn = t;
                ans1 = i+1;
                ans2 = j+1;
            }
        }

    cout << ans1 << ' ' << ans2 << endl;
}

Submission Info

Judge Result