//while (clock()<=69*CLOCKS_PER_SEC) #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define sim template < class c #define ris return * this #define dor > debug & operator << #define eni(x) sim > typename \ enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) { sim > struct rge { c b, e; }; sim > rge<c> range(c i, c j) { return rge<c>{i, j}; } sim > auto dud(c* x) -> decltype(cerr << *x, 0); sim > char dud(...); struct debug { #ifdef LOCAL ~debug() { cerr << endl; } eni(!=) cerr << boolalpha << i; ris; } eni(==) ris << range(begin(i), end(i)); } sim, class b dor(pair < b, c > d) { ris << "(" << d.first << ", " << d.second << ")"; } sim dor(rge<c> d) { *this << "["; for (auto it = d.b; it != d.e; ++it) *this << ", " + 2 * (it == d.b) << *it; ris << "]"; } #else sim dor(const c&) { ris; } #endif }; #define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] " #define shandom_ruffle random_shuffle const int nax=1000*1007; int n, m; long long czas[nax]; int oj[nax]; int roz[nax]; long long wyn[nax]; long long odj; vector <int> zap[nax]; vector < pair<int,int> > merg[nax]; int fin(int v) { if (v!=oj[v]) oj[v]=fin(oj[v]); return oj[v]; } void uni(int a, int b) { if (a>b) swap(a, b); oj[b]=a; roz[a]+=roz[b]; } void moment(int v, int u, long long w) { if (w>=0 && w<nax) merg[w].push_back({v, u}); } inline long long komb(long long v) { return (v*(v-1))/2; } inline long long suf(long long a, long long b) { return (a+b-1)/b; } int main() { scanf("%d%d", &n, &m); for (int i=1; i<=n; i++) scanf("%lld", &czas[i]); for (int i=0; i<=n; i++) { oj[i]=i; roz[i]=1; odj+=czas[i]; } for (int i=1; i<=m; i++) { int x; scanf("%d", &x); zap[x].push_back(i); } for (int i=0; i<n; i++) moment(i, i+1, czas[i+1]-czas[i]); long long sl=0; long long sk=0; sl=odj; for (int i=0; i<nax; i++) { while(!merg[i].empty()) { int x=fin(merg[i].back().first); int y=fin(merg[i].back().second); merg[i].pop_back(); if (x==y) continue; sl-=roz[x]*czas[x]; sl-=roz[y]*czas[y]; sk-=komb(roz[x]); sk-=komb(roz[y]); uni(x, y); sl+=roz[x]*czas[x]; sk+=komb(roz[x]); if (x!=0) { long long dlu=suf(czas[x]-czas[fin(x-1)], roz[fin(x-1)]); moment(fin(x-1), x, dlu); } if (x+roz[x]-1!=n) { long long dlu=suf(czas[x+roz[x]]-czas[x], roz[x]); moment(x, x+roz[x], dlu); } } for (int j : zap[i]) wyn[j]=sl+sk*i-odj; } for (int i=1; i<=m; i++) printf("%lld\n", wyn[i]); return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 | //while (clock()<=69*CLOCKS_PER_SEC) #include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; #define sim template < class c #define ris return * this #define dor > debug & operator << #define eni(x) sim > typename \ enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) { sim > struct rge { c b, e; }; sim > rge<c> range(c i, c j) { return rge<c>{i, j}; } sim > auto dud(c* x) -> decltype(cerr << *x, 0); sim > char dud(...); struct debug { #ifdef LOCAL ~debug() { cerr << endl; } eni(!=) cerr << boolalpha << i; ris; } eni(==) ris << range(begin(i), end(i)); } sim, class b dor(pair < b, c > d) { ris << "(" << d.first << ", " << d.second << ")"; } sim dor(rge<c> d) { *this << "["; for (auto it = d.b; it != d.e; ++it) *this << ", " + 2 * (it == d.b) << *it; ris << "]"; } #else sim dor(const c&) { ris; } #endif }; #define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] " #define shandom_ruffle random_shuffle const int nax=1000*1007; int n, m; long long czas[nax]; int oj[nax]; int roz[nax]; long long wyn[nax]; long long odj; vector <int> zap[nax]; vector < pair<int,int> > merg[nax]; int fin(int v) { if (v!=oj[v]) oj[v]=fin(oj[v]); return oj[v]; } void uni(int a, int b) { if (a>b) swap(a, b); oj[b]=a; roz[a]+=roz[b]; } void moment(int v, int u, long long w) { if (w>=0 && w<nax) merg[w].push_back({v, u}); } inline long long komb(long long v) { return (v*(v-1))/2; } inline long long suf(long long a, long long b) { return (a+b-1)/b; } int main() { scanf("%d%d", &n, &m); for (int i=1; i<=n; i++) scanf("%lld", &czas[i]); for (int i=0; i<=n; i++) { oj[i]=i; roz[i]=1; odj+=czas[i]; } for (int i=1; i<=m; i++) { int x; scanf("%d", &x); zap[x].push_back(i); } for (int i=0; i<n; i++) moment(i, i+1, czas[i+1]-czas[i]); long long sl=0; long long sk=0; sl=odj; for (int i=0; i<nax; i++) { while(!merg[i].empty()) { int x=fin(merg[i].back().first); int y=fin(merg[i].back().second); merg[i].pop_back(); if (x==y) continue; sl-=roz[x]*czas[x]; sl-=roz[y]*czas[y]; sk-=komb(roz[x]); sk-=komb(roz[y]); uni(x, y); sl+=roz[x]*czas[x]; sk+=komb(roz[x]); if (x!=0) { long long dlu=suf(czas[x]-czas[fin(x-1)], roz[fin(x-1)]); moment(fin(x-1), x, dlu); } if (x+roz[x]-1!=n) { long long dlu=suf(czas[x+roz[x]]-czas[x], roz[x]); moment(x, x+roz[x], dlu); } } for (int j : zap[i]) wyn[j]=sl+sk*i-odj; } for (int i=1; i<=m; i++) printf("%lld\n", wyn[i]); return 0; } |