Codeforces Round #345 (Div. 1)

A. Watchmen
두 거리는 좌표 축과 평행한 선의 두 점에서만 동일합니다.겹치는 점에 대해 배척을 허용합니다.

#include <bits/stdc++.h>
#include <unordered_map> 

using namespace std;

#define ll long long

unordered_map<int,ll> xx;
unordered_map<int,ll> yy;

struct point{
    int x;
    int y;
    point(int x,int y):x(x),y(y){

    }
    point(){

    }
};

map<pair<int,int> ,ll> pts;

int main(){

    int n;

    cin>>n;

    for(int i=1;i<=n;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        xx[x]++;
        yy[y]++;
        pts[make_pair(x,y)]++;
    }

    ll ans = 0;

    for(auto it=xx.begin();it!=xx.end();it++){
        ans+= it->second*(it->second-1)/2;
    }

    for(auto it=yy.begin();it!=yy.end();it++){
        ans+= it->second*(it->second-1)/2;
    }

    for(auto it=pts.begin();it!=pts.end();it++){
        ans-= it->second*(it->second-1)/2;
    }

    cout<<ans<<endl;

    return 0;
}

B. Image Preview
방향을 바꾸면 한 번만 바뀔 수 있다는 것을 분석해 보면 알 수 있다.먼저 왼쪽으로 향하는 것과 먼저 오른쪽으로 향하는 상황에 대해 일일이 방향을 바꾸는 위치를 2분으로 뒤져보자.

#include <bits/stdc++.h>
#include <unordered_map> 

using namespace std;

#define ll long long


int n,a,b,t;

int lr[500010];
int rl[500010];

char ori[500010];

int bslr(int k){
    int curt = t;
    curt-=lr[k];
    if(curt<0)return 0;
    curt-=a*(k-1);
    if(curt<=0)return k;


    int r = n+1;
    int l = k+1;
    int finalPos=n+1;
    while(l<=r){
        int mid = (r+l)>>1;
        if(rl[mid]>curt){
            l=mid+1;
        }else{
            finalPos=mid;
            r=mid-1;
        }
    }
    return k+(n+1-finalPos);
}

int ans = 0;

void solve(){
    lr[0] =-a;
    for(int i=1;i<=n;i++){
        lr[i]=lr[i-1];
        lr[i] += a+1;
        if(ori[i]=='w'){
            lr[i]+=b;
        }
    }

    rl[n+1]=0;
    for(int i=n;i>1;i--){
        rl[i]=rl[i+1];
        rl[i] += a+1;
        if(ori[i]=='w'){
            rl[i]+=b;
        }
    }
    rl[n+1]=0;


    for(int i=1;i<=n;i++){
        ans = max(ans,bslr(i));
    }
}

int main(){
    cin>>n>>a>>b>>t;

    scanf("%s",ori+1);

    solve();
    reverse(ori+2,ori+n+1);
    solve();

    cout<<ans<<endl;

    return 0;
}

C. Table Compression
병합이 반드시 같아야 하는 점을 사용하고 값을 정렬해서 작은 것부터 큰 것까지 처리합니다.매번 새로운 점을 처리할 때마다 동업자보다 작은 점을 확보하고 유지보수소가 집합하면 된다.시합할 때 unordered맵 난장판, 전혀 예상치 못하고 검색.

#include <bits/stdc++.h>
#include <unordered_map> 

using namespace std;

#define ll long long

int tab[1000010];

int ans[1000010];

const int maxsz = 1000010;

int rowMax[maxsz];
int colMax[maxsz];

int rowMaxId[maxsz];
int colMaxId[maxsz];


struct node{
    int val;
    int x,y;
    node(int val,int x,int y):val(val),x(x),y(y){
    }
    node(){
    }
    bool operator<(const node &other)const{
        return val<other.val;
    }
}nds[1000010];


int p[1000010];

int find(int x){
    if(p[x]==x)return x;
    int px = find(p[x]);
    return p[x]=px;
}

void Union(int a,int b){
    int pa = find(a);
    int pb = find(b);
    if(pa!=pb){
        p[pb]=pa;
    }
}


int main(){
    int n,m;
    cin>>n>>m;

    int k=1;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            int num;
            scanf("%d",&num);
            nds[k]=node(num,i,j);
            tab[k++]=num;
        }
    }

    int nm=n*m;
    for(int i=0;i<=nm;i++){
        p[i] = i;
    }

    for(int i=0;i<n;i++){
        unordered_map<int,int> mp;
        for(int j=0;j<m;j++){
            int k = i*m+j+1;
            if(mp.count(tab[k])){
                Union(k,mp[tab[k]]);
            }else{
                mp[tab[k]] = k;
            }
        }
    }
    for(int j=0;j<m;j++){
        unordered_map<int,int> mp;
        for(int i=0;i<n;i++){
            int k = i*m+j+1;
            if(mp.count(tab[k])){
                Union(k,mp[tab[k]]);
            }else{
                mp[tab[k]] = k;
            }
        }
    }

    sort(nds+1,nds+nm+1);
    for(int i=1;i<=nm;i++){
        int val = nds[i].val;
        int x = nds[i].x;
        int y = nds[i].y;

        int k = find(x*m+y+1);
        if(rowMax[x]<val){
            ans[k] = max(ans[k],ans[rowMaxId[x]]+1); 
            rowMax[x]=val;
            rowMaxId[x] = k;
        }
        if(colMax[y]<val){
            ans[k] = max(ans[k],ans[colMaxId[y]]+1);
            colMax[y]=val;
            colMaxId[y] = k;
        }
    }

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            int aa = ans[find(i*m+j+1)];
            printf("%d ",aa);
        }
        printf("
");
    }

    return 0;
}