Submission #728317

#TimeUsernameProblemLanguageResultExecution timeMemory
728317myrcellaConstruction of Highway (JOI18_construction)C++17
100 / 100
1257 ms28468 KiB
//by szh #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pii pair<int,int> #define pll pair<long long,long long> #define pb push_back #define debug(x) cerr<<#x<<"="<<x<<endl #define pq priority_queue #define inf 0x3f #define rep(i,a,b) for (int i=a;i<(b);i++) #define MP make_pair #define SZ(x) (int(x.size())) #define ll long long #define mod 1000000007 #define ALL(x) x.begin(),x.end() void inc(int &a,int b) {a=(a+b)%mod;} void dec(int &a,int b) {a=(a-b+mod)%mod;} int lowbit(int x) {return x&(-x);} ll p0w(ll base,ll p) {ll ret=1;while(p>0){if (p%2ll==1ll) ret=ret*base%mod;base=base*base%mod;p/=2ll;}return ret;} const int maxn = 1e5+10; int n; int tree[maxn*4]; int dfn[maxn]; vector <int> edge[maxn]; int w[maxn],ww[maxn]; int st[maxn][17]; pii q[maxn]; int tot = 1; map <int,int> mp; int bit[maxn]; int sz[maxn]; int id[maxn]; void dfs(int u) { dfn[u] = tot++; sz[u] = 1; rep(i,1,17) { if (st[u][i-1]==-1) break; st[u][i] = st[st[u][i-1]][i-1]; } for (int v:edge[u]) dfs(v),sz[u] += sz[v]; } void update(int c,int cl,int cr,int pos,int val) { if (cl==cr) tree[c] = val; else { int mid=cl+cr>>1; if (pos<=mid) update(c<<1,cl,mid,pos,val); else update(c<<1|1,mid+1,cr,pos,val); tree[c] = max(tree[c<<1],tree[c<<1|1]); } return; } void update(int pos,int val) { while (pos<maxn) { bit[pos] += val; pos += lowbit(pos); } return; } int query(int c,int cl,int cr,int l,int r) { if (l<=cl and cr<=r) return tree[c]; int mid=cl+cr>>1; int ret = -1; if (l<=mid) ret = query(c<<1,cl,mid,l,r); if (r>mid) ret = max(ret,query(c<<1|1,mid+1,cr,l,r)); return ret; } int query(int pos) { int ret = 0; while (pos>0) { ret += bit[pos]; pos -= lowbit(pos); } return ret; } int main() { // freopen("input.txt","r",stdin); std::ios::sync_with_stdio(false);cin.tie(0); memset(st,-1,sizeof(st)); memset(tree,-1,sizeof(tree)); cin>>n; rep(i,1,n+1) cin>>w[i],mp[w[i]]=1; for (auto &it:mp) it.se=tot++; tot = 1; rep(i,1,n+1) ww[i] = mp[w[i]]; id[1] = tot++; rep(i,1,n) { int u,v; cin>>u>>v; id[v] = tot++; u = id[u]; v = id[v]; // debug(u),debug(v); q[i] = {u,v}; edge[u].pb(v); st[v][0] = u; } rep(i,1,n+1) w[id[i]] = ww[i]; tot = 1; dfs(1); update(1,1,n,dfn[1],1); rep(qaq,1,n) { int u=q[qaq].fi; // debug(u); int val=query(1,1,n,dfn[u],dfn[u]+sz[u]-1); // debug(val); vector<pii> tmp; while (1) { int cnt = 1; for (int j =16;j>=0;j--) if (st[u][j]!=-1 and query(1,1,n,dfn[st[u][j]],dfn[st[u][j]]+sz[st[u][j]]-1)==val) u = st[u][j],cnt+=(1<<j); tmp.pb({w[val],cnt}); // debug(w[val]);debug(cnt);debug(u);debug(st[u][0]); if (st[u][0]==-1) break; u = st[u][0],val = query(1,1,n,dfn[u],dfn[u]+sz[u]-1); } // debug(SZ(tmp)); ll ans = 0; if (SZ(tmp)>1) { int cnt = 0; for (int i=SZ(tmp)-1;i>=0;i--) { ans += 1ll*(cnt-query(tmp[i].fi))*tmp[i].se; cnt += tmp[i].se; update(tmp[i].fi,tmp[i].se); } for (auto it:tmp) update(it.fi,-it.se); } cout<<ans<<"\n"; update(1,1,n,dfn[q[qaq].se],q[qaq].se); } return 0; }

Compilation message (stderr)

construction.cpp: In function 'void update(int, int, int, int, int)':
construction.cpp:52:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   52 |   int mid=cl+cr>>1;
      |           ~~^~~
construction.cpp: In function 'int query(int, int, int, int, int)':
construction.cpp:70:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |  int mid=cl+cr>>1;
      |          ~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...