| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 763973 |
2023-06-23T04:18:30 Z |
minhcool |
Tents (JOI18_tents) |
C++17 |
|
11 ms |
21380 KB |
#define local
#ifndef local
#include ""
#endif
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
const int N = 3e5 + 5;
const int oo = 1e18 + 7, mod = 1e9 + 7;
mt19937 rng(1);
int rnd(int l, int r){
int temp = rng() % (r - l + 1);
return abs(temp) + l;
}
int n, c[N];
vector<int> Adj[N];
bool ck[N];
int ind[N];
int sz[N];
void dfs(int u){
// cout << u << "\n";
sz[u] = 1;
for(auto v : Adj[u]){
dfs(v);
sz[u] += sz[v];
}
}
int cnt;
int num[N], pos[N], len[N], head[N], par[N];
void hld(int u, int nw){
//cout << u << " " << nw << "\n";
if(nw){
cnt++;
num[u] = cnt; pos[u] = 1;
head[cnt] = u;
}
ii mx = {-1, -1};
for(auto v : Adj[u]) mx = max(mx, {sz[v], v});
if(mx.fi < 0) return;
num[mx.se] = num[u]; pos[mx.se] = pos[u] + 1;
hld(mx.se, 0);
for(auto v : Adj[u]) if(v != mx.se) hld(v, 1);
}
set<ii> segs[N];// start_pos & c[i]
int bit[N], posi[N];
vector<int> used;
void upd(int id, int val){
used.pb(id);
for(; id <= n; id += id & -id){
bit[id] += val;
// cout << id << " " << n << " " << "OK\n";
}
}
int get(int id){
int ans = 0;
for(; id; id -= id & -id) ans += bit[id];
return ans;
}
int answer = 0;
void upd(int id){
int savee = posi[id];
while(id){
set<ii>::iterator it = segs[num[id]].upper_bound({pos[id], oo});
//int tempo = (it == segs[num[id]].end() ? len[num[id]] : (*it).fi - 1);
it--;
// id = par[head[num[id]]];
//cout << id << "\n";
// continue;
int lst = (*it).se, lstt = pos[id] + 1;
vector<ii> v;
for(; ; it--){
v.pb((*it));
//assert((*it).se != 0);
// cout << "HEHEHE " << (*it).se << "\n";
// cout << lstt << " " << (*it).fi << "\n";
// cout << (*it).fi << " " << (*it).se << " " << (lstt - (*it).fi) << " " << get((*it).se - 1) << "\n";
answer += (lstt - (*it).fi) * get((*it).se - 1);
upd((*it).se, (lstt - (*it).fi));
if(it == segs[num[id]].begin()) break;
lstt = (*it).fi;
}
// id = par[head[num[id]]];
// continue;
for(auto it : v) segs[num[id]].erase(it);
segs[num[id]].insert({1, savee});
segs[num[id]].insert({pos[id] + 1, lst});
id = par[head[num[id]]];
}
}
#ifdef local
void process(){
cin >> n;
vector<int> diff;
for(int i = 1; i <= n; i++){
cin >> c[i];
diff.pb(c[i]);
}
diff.pb(-1);
sort(diff.begin(), diff.end());
diff.resize(unique(diff.begin(), diff.end()) - diff.begin());
for(int i = 1; i <= n; i++) posi[i] = lower_bound(diff.begin(), diff.end(), c[i]) - diff.begin();
ck[1] = 1;
for(int i = 1; i < n; i++){
int x, y;
cin >> x >> y;
if(!ck[x]){
//cout << x << "\n";
Adj[y].pb(x);
par[x] = y;
ck[x] = 1;
ind[i] = x;
}
else{
Adj[x].pb(y);
par[y] = x;
ck[y] = 1;
ind[i] = y;
}
}
dfs(1);
hld(1, 1);
for(int i = 1; i <= n; i++){
len[num[i]] = max(len[num[i]], pos[i]);
segs[i].insert({1, n});
}
//return;
for(int i = 1; i < n; i++){
answer = 0;
upd(ind[i]);
cout << answer << "\n";
for(auto it : used){
int temp = it;
for(; temp <= n; temp += temp & -temp) bit[temp] = 0;
}
used.clear();
}
}
signed main(){
//ios_base::sync_with_stdio(0);
//cin.tie(0);
process();
}
#endif
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
21380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
21380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
