제출 #409592

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
409592		urd05	Construction of Highway (JOI18_construction)	C++14	16 / 100	2084 ms	25276 KiB

construction

#include <bits/stdc++.h>
using namespace std;

int n;
int arr[100000];
vector<int> adj[100000];
typedef pair<int,int> P;
P edge[100000];
int p[100000];
int ind[100000];
int siz[100000];
int f=0;
int depth[100000];
int par[100000][17];

void dfs(int v,int prev) {
    ind[v]=f++;
    siz[v]=1;
    p[v]=prev;
    for(int i=0;i<adj[v].size();i++) {
        int nt=adj[v][i];
        if (nt==prev) {
            continue;
        }
        depth[nt]=depth[v]+1;
        dfs(nt,v);
        siz[v]+=siz[nt];
    }
}

const int sz=131072;
P seg[sz*2];

P pmax(P a,P b) {
    return a<b?b:a;
}

P sum(int l,int r,int node=1,int nodel=0,int noder=sz-1) {
    if (r<nodel||l>noder) {
        return P(0,0);
    }
    if (l<=nodel&&noder<=r) {
        return seg[node];
    }
    int mid=(nodel+noder)/2;
    return pmax(sum(l,r,node*2,nodel,mid),sum(l,r,node*2+1,mid+1,noder));
}

void update(int i,P val) {
    i+=sz;
    seg[i]=val;
    while (i>1) {
        i/=2;
        seg[i]=pmax(seg[i*2],seg[i*2+1]);
    }
}

struct SegmentTree {
    vector<int> seg;
    int sz=1;
    void init(int x) {
        while (sz<x) {
            sz*=2;
        }
        seg.resize(sz*2);
    }
    int sum(int l,int r,int node=1,int nodel=0,int noder=0) {
        if (node==1) {
            noder=sz-1;
        }
        if (r<nodel||l>noder) {
            return 0;
        }
        if (l<=nodel&&noder<=r) {
            return seg[node];
        }
        int mid=(nodel+noder)/2;
        return sum(l,r,node*2,nodel,mid)+sum(l,r,node*2+1,mid+1,noder);
    }
    void update(int i,int val) {
        i+=sz;
        seg[i]+=val;
        while (i>1) {
            i/=2;
            seg[i]=seg[i*2]+seg[i*2+1];
        }
    }
};

long long cntinv(vector<P> v) {
    vector<int> press;
    for(int i=0;i<v.size();i++) {
        //printf("%d %d\n",v[i].first,v[i].second);
        press.push_back(v[i].first);
    }
    sort(press.begin(),press.end());
    press.erase(unique(press.begin(),press.end()),press.end());
    SegmentTree st;
    st.init(press.size());
    long long ret=0;
    for(int i=0;i<v.size();i++) {
        v[i].first=lower_bound(press.begin(),press.end(),v[i].first)-press.begin();
        if (v[i].first!=0)
            ret+=1LL*v[i].second*st.sum(0,v[i].first-1);
        st.update(v[i].first,v[i].second);
    }
    return ret;
}

int main(void) {
    scanf("%d",&n);
    for(int i=0;i<n;i++) {
        scanf("%d",&arr[i]);
    }
    vector<int> press;
    for(int i=0;i<n;i++) {
        press.push_back(arr[i]);
    }
    sort(press.begin(),press.end());
    press.erase(unique(press.begin(),press.end()),press.end());
    for(int i=0;i<n;i++) {
        arr[i]=lower_bound(press.begin(),press.end(),arr[i])-press.begin();
    }
    for(int i=1;i<n;i++) {
        int u,v;
        scanf("%d %d",&u,&v);
        u--;
        v--;
        edge[i]=P(u,v);
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(0,-1);
    memset(par,-1,sizeof(par));
    for(int i=0;i<n;i++) {
        par[i][0]=p[i];
    }
    for(int j=1;j<17;j++) {
        for(int i=0;i<n;i++) {
            if (par[i][j-1]!=-1) {
                par[i][j]=par[par[i][j-1]][j-1];
            }
        }
    }
    for(int i=1;i<n;i++) {
        int now=edge[i].first;
        vector<P> vec;
        while (now!=-1) {
            int rec=now;
            int deep=sum(ind[now],ind[now]+siz[now]-1).second;
            for(int j=16;j>=0;j--) {
                int nt=par[rec][j];
                if (nt==-1) {
                    continue;
                }
                if (sum(ind[nt],ind[nt]+siz[nt]-1).second==deep) {
                    rec=nt;
                }
            }
            vec.push_back(P(arr[deep],depth[now]-depth[rec]+1));
            now=p[rec];
        }
        update(ind[edge[i].second],P(i,edge[i].second));
        printf("%lld\n",cntinv(vec));
    }
}

컴파일 시 표준 에러 (stderr) 메시지

construction.cpp: In function 'void dfs(int, int)':
construction.cpp:20:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(int i=0;i<adj[v].size();i++) {
      |                 ~^~~~~~~~~~~~~~
construction.cpp: In function 'long long int cntinv(std::vector<std::pair<int, int> >)':
construction.cpp:92:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |     for(int i=0;i<v.size();i++) {
      |                 ~^~~~~~~~~
construction.cpp:101:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for(int i=0;i<v.size();i++) {
      |                 ~^~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:111:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
construction.cpp:113:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         scanf("%d",&arr[i]);
      |         ~~~~~^~~~~~~~~~~~~~
construction.cpp:126:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         scanf("%d %d",&u,&v);
      |         ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 0 / 84