Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>
using namespace std;
int n;
vector<int> a;
inline bool read() {
if(!(cin >> n))
return false;
a.resize(n);
for(int i = 0; i < n; i++) {
cin >> a[i];
a[i]--;
}
return true;
}
inline void solve() {
int cnt = 0, pos = 0;
while(pos < n) {
cnt++;
int mx = pos;
while(pos < n && pos <= mx) {
mx = max(mx, a[pos]);
pos++;
}
}
cout << cnt << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
#endif
if(read()) {
solve();
}
return 0;
}
Tutorial
Tutorial is loading...
Solution (Roms)
#include <bits/stdc++.h>
using namespace std;
int t, n;
string s;
int main(){
cin >> t;
for(int tc = 0; tc < t; ++tc){
cin >> n >> s;
int res = n - 1;
for(int i = 0; i < n; ++i)
if(s[i] == '>' || s[n - 1 - i] == '<')
res = min(res, i);
cout << res << endl;
}
return 0;
}
Tutorial
Tutorial is loading...
Solution (Roms)
#include <bits/stdc++.h>
using namespace std;
const int N = 300009;
int n, k;
pair<int, int> a[N];
int main() {
cin >> n >> k;
for(int i = 0; i < n; ++i)
cin >> a[i].second >> a[i].first;
sort(a, a + n);
long long res = 0;
long long sum = 0;
set<pair<int, int> > s;
for(int i = n - 1; i >= 0; --i){
s.insert(make_pair(a[i].second, i));
sum += a[i].second;
while(s.size() > k){
auto it = s.begin();
sum -= it->first;
s.erase(it);
}
res = max(res, sum * a[i].first);
}
cout << res << endl;
return 0;
}
Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>
using namespace std;
int main() {
int n; cin >> n;
long long ans = 0;
for(int id = 2; id < n; id++)
ans += 1ll * id * (id + 1);
cout << ans << endl;
}
1140E - Palindrome-less Arrays
Tutorial
Tutorial is loading...
Solution (adedalic)
#include<bits/stdc++.h>
using namespace std;
#define fore(i, l, r) for(int i = int(l); i < int(r); i++)
#define sz(a) int((a).size())
#define x first
#define y second
typedef long long li;
typedef pair<int, int> pt;
const int MOD = 998244353;
int norm(int a) {
while(a >= MOD) a -= MOD;
while(a < 0) a += MOD;
return a;
}
int mul(int a, int b) {
return int(a * 1ll * b % MOD);
}
int n, k;
vector<int> a;
inline bool read() {
if(!(cin >> n >> k))
return false;
a.resize(n);
fore(i, 0, n)
cin >> a[i];
return true;
}
pair<int, int> calc(int len) {
if(len == 0) return {0, 1};
if(len & 1) {
auto res = calc(len >> 1);
return {norm(mul(res.x, res.x) + mul(k - 1, mul(res.y, res.y))),
norm(mul(2, mul(res.x, res.y)) + mul(k - 2, mul(res.y, res.y)))};
}
auto res = calc(len - 1);
return {mul(k - 1, res.y), norm(res.x + mul(k - 2, res.y))};
}
vector<int> curArray;
int calcSeg(int l, int r) {
if(r >= sz(curArray)) {
int len = r - l - 1, cf = 1;
if(l < 0)
len--, cf = k;
if(len == 0) return cf;
auto res = calc(len - 1);
return mul(cf, norm(res.x + mul(k - 1, res.y)));
}
if(l < 0) {
if(r - l == 1) return 1;
auto res = calc(r - l - 2);
return norm(res.x + mul(k - 1, res.y));
}
auto res = calc(r - l - 1);
return curArray[l] == curArray[r] ? res.x : res.y;
}
inline void solve() {
int ans = 1;
fore(k, 0, 2) {
curArray.clear();
for(int i = 0; 2 * i + k < n; i++)
curArray.push_back(a[2 * i + k]);
int lst = -1;
fore(i, 0, sz(curArray)){
if(curArray[i] == -1) continue;
ans = mul(ans, calcSeg(lst, i));
lst = i;
}
ans = mul(ans, calcSeg(lst, sz(curArray)));
}
cout << ans << endl;
}
int main() {
#ifdef _DEBUG
freopen("input.txt", "r", stdin);
int tt = clock();
#endif
ios_base::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cout << fixed << setprecision(15);
if(read()) {
solve();
#ifdef _DEBUG
cerr << "TIME = " << clock() - tt << endl;
tt = clock();
#endif
}
return 0;
}
1140F - Extending Set of Points
Tutorial
Tutorial is loading...
Solution (BledDest)
#include <bits/stdc++.h>
using namespace std;
typedef long long li;
#define x first
#define y second
const int N = 300043;
const int K = 300000;
int p[2 * N];
int s1[2 * N];
int s2[2 * N];
li ans = 0;
int* where[80 * N];
int val[80 * N];
int cur = 0;
void change(int& x, int y)
{
where[cur] = &x;
val[cur] = x;
x = y;
cur++;
}
void rollback()
{
cur--;
(*where[cur]) = val[cur];
}
int get(int x)
{
if(p[x] == x)
return x;
return get(p[x]);
}
void merge(int x, int y)
{
x = get(x);
y = get(y);
if(x == y) return;
ans -= s1[x] * 1ll * s2[x];
ans -= s1[y] * 1ll * s2[y];
if(s1[x] + s2[x] < s1[y] + s2[y])
swap(x, y);
change(p[y], x);
change(s1[x], s1[x] + s1[y]);
change(s2[x], s2[x] + s2[y]);
ans += s1[x] * 1ll * s2[x];
}
void init()
{
for(int i = 0; i < K; i++)
{
p[i] = i;
p[i + K] = i + K;
s1[i] = 1;
s2[i + K] = 1;
}
}
vector<pair<int, int> > T[4 * N];
void add(int v, int l, int r, int L, int R, pair<int, int> val)
{
if(L >= R) return;
if(L == l && R == r)
T[v].push_back(val);
else
{
int m = (l + r) / 2;
add(v * 2 + 1, l, m, L, min(R, m), val);
add(v * 2 + 2, m, r, max(m, L), R, val);
}
}
li res[N];
void dfs(int v, int l, int r)
{
li last_ans = ans;
int state = cur;
for(auto x : T[v])
merge(x.x, x.y + K);
if(l == r - 1)
res[l] = ans;
else
{
int m = (l + r) / 2;
dfs(v * 2 + 1, l, m);
dfs(v * 2 + 2, m, r);
}
while(cur != state) rollback();
ans = last_ans;
}
int main()
{
int q;
scanf("%d", &q);
map<pair<int, int>, int> last;
for(int i = 0; i < q; i++)
{
int x, y;
scanf("%d %d", &x, &y);
--x;
--y;
pair<int, int> p = make_pair(x, y);
if(last.count(p))
{
add(0, 0, q, last[p], i, p);
last.erase(p);
}
else
last[p] = i;
}
for(auto x : last)
add(0, 0, q, x.y, q, x.x);
init();
dfs(0, 0, q);
for(int i = 0; i < q; i++)
printf("%I64d ", res[i]);
}
Tutorial
Tutorial is loading...
Solution (BledDest)
#include <bits/stdc++.h>
using namespace std;
typedef long long li;
#define x first
#define y second
const int N = 600043;
li d1[N];
li d2[N][2];
li dist_temp[N][2];
vector<pair<int, int> > g[N];
vector<int> qs[N];
int qq[N][2];
li ans[N];
int n;
int used[N];
int cnt[N];
int last[N];
int cc = 1;
void preprocess()
{
set<pair<li, int> > q;
for(int i = 0; i < n; i++)
q.insert(make_pair(d1[i], i));
while(!q.empty())
{
int k = q.begin()->second;
q.erase(q.begin());
for(auto e : g[k])
{
int to = e.first;
li w = d2[e.second][0] + d2[e.second][1];
if(d1[to] > w + d1[k])
{
q.erase(make_pair(d1[to], to));
d1[to] = w + d1[k];
q.insert(make_pair(d1[to], to));
}
}
}
}
void dfs1(int x, int p = -1)
{
if(used[x]) return;
cnt[x] = 1;
for(auto y : g[x])
{
int to = y.first;
if(!used[to] && to != p)
{
dfs1(to, x);
cnt[x] += cnt[to];
}
}
}
vector<int> cur_queries;
pair<int, int> c;
int S = 0;
void find_centroid(int x, int p = -1)
{
if(used[x]) return;
int mx = 0;
for(auto y : g[x])
{
int to = y.first;
if(!used[to] && to != p)
{
find_centroid(to, x);
mx = max(mx, cnt[to]);
}
}
if(p != -1)
mx = max(mx, S - cnt[x]);
c = min(c, make_pair(mx, x));
}
void dfs2(int x, int p = -1, int e = -1)
{
if(used[x]) return;
if(p == -1)
{
dist_temp[x * 2][0] = dist_temp[x * 2 + 1][1] = 0ll;
dist_temp[x * 2][1] = dist_temp[x * 2 + 1][0] = d1[x];
}
else
{
for(int k = 0; k < 2; k++)
{
li& D0 = dist_temp[x * 2][k];
li& D1 = dist_temp[x * 2 + 1][k];
D0 = dist_temp[p * 2][k] + d2[e][0];
D1 = dist_temp[p * 2 + 1][k] + d2[e][1];
D0 = min(D0, D1 + d1[x]);
D1 = min(D1, D0 + d1[x]);
}
}
for(auto y : qs[x])
{
if(ans[y] != -1) continue;
if(last[y] == cc)
cur_queries.push_back(y);
else
last[y] = cc;
}
for(auto y : g[x])
{
int to = y.first;
if(!used[to] && to != p)
dfs2(to, x, y.second);
}
}
void centroid(int v)
{
if(used[v]) return;
dfs1(v);
S = cnt[v];
c = make_pair(int(1e9), -1);
find_centroid(v);
int C = c.second;
used[C] = 1;
for(auto y : g[C])
centroid(y.first);
cc++;
cur_queries.clear();
used[C] = 0;
dfs2(C);
for(auto x : cur_queries)
{
int u = qq[x][0];
int v = qq[x][1];
ans[x] = min(dist_temp[u][0] + dist_temp[v][0], dist_temp[u][1] + dist_temp[v][1]);
}
}
int main()
{
scanf("%d", &n);
for(int i = 0; i < n; i++)
scanf("%I64d", &d1[i]);
for(int i = 0; i < n - 1; i++)
{
int x, y;
li w1, w2;
scanf("%d %d %I64d %I64d", &x, &y, &w1, &w2);
--x;
--y;
d2[i][0] = w1;
d2[i][1] = w2;
g[x].push_back(make_pair(y, i));
g[y].push_back(make_pair(x, i));
}
int q;
scanf("%d", &q);
for(int i = 0; i < q; i++)
{
scanf("%d", &qq[i][0]);
scanf("%d", &qq[i][1]);
--qq[i][0];
--qq[i][1];
qs[qq[i][0] / 2].push_back(i);
qs[qq[i][1] / 2].push_back(i);
}
preprocess();
for(int i = 0; i < q; i++)
ans[i] = -1;
centroid(0);
for(int i = 0; i < q; i++)
cout << ans[i] << endl;
}