二問

あみだくじ条件見逃してて
ペイントカラーは実装力がなさすぎた…

0540

1〜kまで連続って…じゃあ簡単やん…

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
struct amida {
    int a, b;
};
bool comp(const amida& a, const amida& b) {
    return a.b<b.b;
}
int n, m, h, k;
int sc[1000], num[1000], res[1000];
amida ami[100000], scs[100000], ns[100000];
int main() {
    while (scanf("%d%d%d%d",&n,&m,&h,&k)) {
        if (!n&&!m&&!h&&!k) break;
        for (int i=0; i<n; i++) scanf("%d",&sc[i]);
        for (int i=0; i<m; i++) {
            scanf("%d%d",&ami[i].a,&ami[i].b);
        }
        sort(ami, ami+m, comp);
        for (int i=0; i<n; i++) num[i]=i;
        // number
        for (int i=0; i<m; i++) {
            ns[i].a=num[ami[i].a-1];
            ns[i].b=num[ami[i].a];
            swap(num[ami[i].a-1], num[ami[i].a]);
        }
        // score
        for (int i=m-1; i>=0; i--) {
            scs[i].a=sc[ami[i].a-1];
            scs[i].b=sc[ami[i].a];
            swap(sc[ami[i].a-1], sc[ami[i].a]);
        }
        // calc
        memset(res, 0, sizeof(res));
        int d=0;
        for (int i=0; i<m; i++) {
            res[ns[i].a]=scs[i].b;
            res[ns[i].b]=scs[i].a;
            if (0<=ns[i].a&&ns[i].a<k&&0<=ns[i].b&&ns[i].b<k) {
                continue;
            } else if (0<=ns[i].a&&ns[i].a<k) {
                d=min(d, scs[i].a-scs[i].b);
            } else if (0<=ns[i].b&&ns[i].b<k) {
                d=min(d, scs[i].b-scs[i].a);
            }
        }
        //printf("%d\n",d);
        ll ans=d;
        for (int i=0; i<k; i++) ans+=res[i];
        printf("%lld\n",ans);
    }
}

0531

座圧ようやく理解…
ちょっと蟻本のサンプルコードわかりにくすぎな気が…
まぁいいや

#include <cstdio>
#include <cstring>
#include <vector>
#include <map>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int, int> P;
int w, h, n;
int x1[1000],x2[1000],y1[1000],y2[1000];
bool mp[3000][3000];
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int main() {
    while (scanf("%d%d",&w,&h)) {
        if (!w&&!h) break;
        scanf("%d",&n);
        vector<int> x, y;
        for (int i=0; i<n; i++) {
            scanf("%d%d%d%d",&x1[i],&y1[i],&x2[i],&y2[i]);
            x.push_back(x1[i]); x.push_back(x2[i]);
            y.push_back(y1[i]); y.push_back(y2[i]);
        }
        x.push_back(0); x.push_back(w);
        y.push_back(0); y.push_back(h);
        sort(x.begin(), x.end());
        sort(y.begin(), y.end());
        x.erase(unique(x.begin(),x.end()), x.end());
        y.erase(unique(y.begin(),y.end()), y.end());
        int X=x.size(), Y=y.size();
        for (int i=0; i<n; i++) {
            x1[i]=lower_bound(x.begin(),x.end(),x1[i])-x.begin();
            x2[i]=lower_bound(x.begin(),x.end(),x2[i])-x.begin();
            y1[i]=lower_bound(y.begin(),y.end(),y1[i])-y.begin();
            y2[i]=lower_bound(y.begin(),y.end(),y2[i])-y.begin();
        }
        for (int i=0; i<Y; i++) for (int j=0; j<X; j++) mp[i][j]=i==Y-1||j==X-1;
        for (int i=0; i<n; i++) {
            for (int j=x1[i]; j<x2[i]; j++) {
                for (int k=y1[i]; k<y2[i]; k++) mp[k][j]=1;
            }
        }
        // for (int i=0; i<Y; i++) for (int j=0; j<X; j++) printf("%d%c",mp[i][j]?1:0,j==X-1?'\n':' ');
        int ans=0;
        for (int i=0; i<Y; i++) {
            for (int j=0; j<X; j++) {
                if (mp[i][j]) continue;
                ans++;
                mp[i][j]=1;
                queue<P> que;
                que.push(P(i,j));
                while (!que.empty()) {
                    int a=que.front().first, b=que.front().second; que.pop();
                    // printf("%d %d\n",a,b);
                    for (int k=0; k<4; k++) {
                        int nx=b+dx[k], ny=a+dy[k];
                        if (nx<0||nx>=X-1||ny<0||ny>=Y-1||mp[ny][nx]) continue;
                        mp[ny][nx]=1;
                        que.push(P(ny,nx));
                    }
                }
            }
        }
        printf("%d\n",ans);
    }
}