Настройки поиска

#include <cstdio>
#include <vector>

using namespace std;

#define Size(x) (int)(x).size()
#define For(i,a,b) for(int i=(int)(a);i<=(int)(b);++i)
#define RepV(i,v) for (int i=0;i<Size(v);++i)
#define Fill(a,b) memset(&a,b,sizeof(a))

int n, m, v[1005], xy[1005], yx[1005];
vector<int> x[1005];

int go(int u){
    if ( v[u]++ ) return 0;
    
    RepV(i, x[u]) if ( !yx[x[u][i]] || go( yx[x[u][i]] ) ) {
        xy[u] = x[u][i];
        yx[x[u][i]] = u;
        return 1;
    }
    
    return 0;
}

int main(){
    int k;
    scanf("%d%d%d", &n, &m, &k);
    
    For(i, 1, k) {
        int a, b;
        scanf("%d%d", &a, &b);
        x[a].push_back(b);
    }
    
    int max_bipartite_matching = 0;
    For(i, 1, n) if ( !xy[i] ) {
        Fill(v, 0);
        max_bipartite_matching += go(i);
    }
    
    printf("%d", n + m - max_bipartite_matching );
    
    return 0;
}

long long solve(long long n){
    int sq = sqrt((double)n);
    long long st = n/sq;

    long long l = sq, r = sq + 100000000;
    if (n/l == n/(l+1)) return l;
    while (n/l-n/(l+1) > 1) ++l;
    if (n/l == n/(l+1)) return l;
    st = n/l;
    sq=l;

    while (l+1<r){
        long long m = (l+r)/2;
        long long srx = n/m;
        if (st-srx == m - sq) l=m; else r=m;
    }

    return l;
}

#include <iostream> 
#include <algorithm> 
#include <vector> 
#include <set> 

using namespace std;

#define Size(x) (int)(x).size()
#define For(i,a,b) for(int i=(int)(a);i<=(int)(b);++i)
#define RepV(i,v) for (int i=0;i<Size(v);++i)

struct state{
    int x, level;
    char start, color;
    state(int x, int level, char start, char color):x(x),level(level),start(start),color(color){}
};

bool by_x(state& a, state& b){
    if (a.x!=b.x) return a.x < b.x;
    if (a.start != b.start) return a.start < b.start;
    return a.level < b.level;
}

int main(){
    vector<state> states;
    states.push_back(state(0,0,1,'w'));
    states.push_back(state(1000000000,0,0,'w'));
    int n;
    scanf("%d",&n);
    For(i,1,n){
        int a, b;
        char c;
        scanf("%d%d %c\n",&a,&b,&c);
        states.push_back(state(a,i,1,c));
        states.push_back(state(b,i,0,c));
    }

    sort(states.begin(),states.end(),by_x);

    vector<pair<int,int> >wlist;
    set<int> w, b;
    RepV(i,states){
        state cur = states[i];
        char color='b';
        if (Size(b)==0 || ( Size(w)>0 && *b.rbegin() < *w.rbegin())){
            color='w';
        }
        if (color=='w'){
            if (i>0)
                wlist.push_back(make_pair(states[i-1].x,cur.x));
        }
        if (!cur.start)
            if (cur.color=='w') w.erase(w.find(cur.level));
            else b.erase(b.find(cur.level));
        else
            if (cur.color=='w') w.insert(cur.level);
            else b.insert(cur.level);
    }

    int len = 0, left = 0;

    int l=-1,r=-1;
    RepV(i,wlist){
        if (wlist[i].first == r) {
            r = wlist[i].second;
        } else {
            if (r-l > len){
                len = r-l;
                left=l;
            }
            l=wlist[i].first;
            r=wlist[i].second;
        }
    }

    if (r-l > len){
        len = r-l;
        left=l;
    }
    printf("%d %d",left,left + len);

    return 0;
}