Tutorial is loading...
Code
#include <iostream>
#include <vector>
using namespace std;
int main() {
int N; cin >> N;
vector<int> A(N); for (int&a:A) cin >> a;
vector<int> P{1};
int rest = 0, cur = A[0];
for (int i = 1; i < N; ++i) {
if (A[i] <= A[0]/2) {
cur += A[i];
P.push_back(i+1);
} else {
rest += A[i];
}
}
if (cur > rest) {
cout << P.size() << endl;
for (int i = 0; i < P.size(); ++i) cout << P[i] << " \n"[i==P.size()-1];
} else {
cout << 0 << endl;
}
}
Tutorial is loading...
Code
#include <iostream>
#include <string>
using namespace std;
typedef long long ll;
int main() {
string S; cin >> S;
ll a = 0, b = 0, c = 0;
for (int i = 0; i < S.size(); ++i) {
if (S[i] == 'o') {
b += a;
} else if (i > 0 && S[i-1] == 'v') {
a++;
c += b;
}
}
cout << c << endl;
}
Tutorial is loading...
Code
#include <iostream>
using namespace std;
constexpr int MOD = 998244353;
int main() {
int R, C; cin >> R >> C;
int X = 1;
while (R--) X = (2*X)%MOD;
while (C--) X = (2*X)%MOD;
cout << X << endl;
}
Tutorial is loading...
Code
#include <iostream>
using namespace std;
bool prime(int x) {
if (x < 2) return false;
for (int i = 2; i*i <= x; ++i) {
if (x%i == 0) return false;
}
return true;
}
int main(int argc, char ** argv){
int n; cin >> n;
int m = n;
while (!prime(m)) ++m;
cout << m << "\n1 " << n << '\n';
for (int i = 0; i < n-1; ++i) {
cout << i+1 << ' ' << i+2 << '\n';
}
for (int i = 0; i < m-n; ++i) {
cout << i+1 << ' ' << i+1+n/2 << '\n';
}
}
Tutorial is loading...
Code
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main() {
string S; cin >> S;
int N = S.size();
int i = 0, j = N-1;
string A;
while (j-i >= 3) {
if (S[i] == S[j]) {
A.push_back(S[i]);
++i; --j;
} else if (S[i] == S[j-1]) {
A.push_back(S[i]);
++i; j -= 2;
} else {
A.push_back(S[i+1]);
if (S[i+1] == S[j]) {
--j;
} else {
j -= 2;
}
i += 2;
}
}
string B = A;
if (j >= i) A.push_back(S[i]);
reverse(B.begin(),B.end());
cout << A << B << endl;
}
Tutorial is loading...
Code
#include <iostream>
#include <vector>
using namespace std;
template <unsigned int N> class Field {
typedef unsigned int ui;
typedef unsigned long long ull;
public:
inline Field(int x = 0) : v(x) {}
inline Field<N>&operator+=(const Field<N>&o) {if (v+o.v >= N) v += o.v - N; else v += o.v; return *this; }
inline Field<N>&operator*=(const Field<N>&o) {v=(ull)v*o.v % N; return *this; }
inline Field<N> operator*(const Field<N>&o) const {Field<N>r{*this};return r*=o;}
inline explicit operator ui() const { return v; }
private: ui v;
};
template<unsigned int N>ostream &operator<<(std::ostream&os,const Field<N>&f){return os<<(unsigned int)f;}
template<unsigned int N>Field<N> operator*(int i,const Field<N>&f){return Field<N>(i)*f;}
typedef Field<998244353> F;
int main() {
ios_base::sync_with_stdio(false);
int N, M; cin >> N >> M;
vector<int> C(N); for (int &c: C) { cin >> c; --c; }
vector<vector<F>> D(N+1, vector<F>(N+1, 1));
for (int l = 1; l <= M; ++l) {
for (int a = 0; a + l <= M; ++a) {
pair<int,int> lo = {C[a],0};
for (int i = 0; i < l; ++i) lo = min(lo, {C[a+i],i});
int j = lo.second;
if (j < 0 || j >= l) { D[a][l] = 0; continue; }
F left = 0, right = 0;
for (int u = 0; u <= j; ++u) left += D[a][u] * D[a+u][j-u];
for (int v = j+1; v <= l; ++v) right += D[a+j+1][v-(j+1)] * D[a+v][l-v];
D[a][l] = left * right;
}
}
cout << D[0][N] << endl;
}
Tutorial is loading...
Code
#include <iostream>
#include <vector>
using namespace std;
template <unsigned int N> class Field {
typedef unsigned int ui;
typedef unsigned long long ull;
public:
inline Field(int x = 0) : v(x) {}
inline Field<N> pow(int p){return (*this)^p; }
inline Field<N>&operator+=(const Field<N>&o) {if (v+o.v >= N) v += o.v - N; else v += o.v; return *this; }
inline Field<N>&operator*=(const Field<N>&o) {v=(ull)v*o.v % N; return *this; }
inline Field<N> operator*(const Field<N>&o) const {Field<N>r{*this};return r*=o;}
inline explicit operator ui() const { return v; }
private: ui v;
};
template<unsigned int N>ostream &operator<<(std::ostream&os,const Field<N>&f){return os<<(unsigned int)f;}
template<unsigned int N>Field<N> operator+(int i,const Field<N>&f){return Field<N>(i)+f;}
template<unsigned int N>Field<N> operator*(int i,const Field<N>&f){return Field<N>(i)*f;}
typedef Field<998244353> F;
int main() {
ios_base::sync_with_stdio(false);
int N, M; cin >> N >> M;
vector<int> C(M); for (int &c: C) { cin >> c; --c; }
vector<int> W;
for (int i = 0; i < M; ++i) if (W.empty() || W.back() != C[i]) W.push_back(C[i]);
M = W.size();
if (M > 2*N) { cout << "0\n"; return 0; }
vector<vector<int>> E(N);
for (int i = 0; i < M; ++i) E[W[i]].push_back(i);
vector<vector<F>> D(M+1, vector<F>(M+1, 1));
for (int l = 1; l <= M; ++l) {
for (int a = 0; a + l <= M; ++a) {
int lo = W[a];
for (int i = 0; i < l; ++i) lo = min(lo, W[a+i]);
int j = E[lo][0] - a;
int k = E[lo].back() - a;
if (j < 0 || k >= l) { D[a][l] = 0; continue; }
F left = 0, right = 0;
for (int u = 0; u <= j; ++u) left += D[a][u] * D[a+u][j-u];
for (int v = k+1; v <= l; ++v) right += D[a+k+1][v-(k+1)] * D[a+v][l-v];
D[a][l] = left * right;
for (int m = 0; m < E[lo].size()-1; ++m) {
if (E[lo][m] + 1 != E[lo][m+1]) {
D[a][l] *= D[E[lo][m]+1][E[lo][m+1] - E[lo][m] - 1];
}
}
}
}
cout << D[0][M] << endl;
}
Tutorial is loading...
Code
#include <vector>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cassert>
#include <cmath>
using namespace std;
#define x first
#define y second
typedef std::pair<int,int> pii; typedef long long ll; typedef unsigned long long ull; typedef unsigned int ui; typedef pair<ui,ui> puu;
template<typename T>std::istream&operator>>(std::istream&i,vector<T>&t) {for(auto&v:t){i>>v;}return i;}
template <typename T> bool in(T a, T b, T c) { return a <= b && b < c; }
bool fractionGreaterOrEqual(double a, double b, double c, double d) {
return a/b >= c/d;
}
int TOTAL;
/* UpperEnvelope that with O(N) build and amortized O(1) query.
* The updates need be sorted by (m,b), the queries need to be sorted by x, and
* updates need to come before queries. */
namespace LinearEnvelope {
template<typename T> struct Line { T m, b; int id; };
template <typename T>
struct Upper {
Line<T> *V;
T t; int i, s;
Upper(int w) : V(new Line<T>[w]), t(0), i(0), s(0) { TOTAL++; }
~Upper() { TOTAL--; }
//~Upper() { delete []V; }
void clear() { i = s = 0; t = 0; }
void insert_line(T m, T b, int i = 0) {
assert(t == 0);
if (s > 0 && V[s-1].m == m && V[s-1].b >= b) return;
while (s > 0 && ((V[s-1].b < b) || (V[s-1].b == b && V[s-1].m < m))) --s;
while (s >= 2 && fractionGreaterOrEqual(V[s-2].b - V[s-1].b, V[s-1].m - V[s-2].m, V[s-1].b - b, m - V[s-1].m)) --s;
V[s++] = {m,b,i};
}
pair<T,int> advance(T x) {
assert(x >= 0);
t += x;
while (i+1 < s && V[i].m * t + V[i].b < V[i+1].m * t + V[i+1].b) ++i;
return {V[i].m * t + V[i].b, V[i].id};
}
};
};
class RPPS {
public:
vector<vector<int>> E;
vector<ll> A,B,RA,RB;
vector<int> Enter,Exit;
int T;
void dfs(int u, ll a, ll b) {
A[u] += a;
B[u] += b;
Enter[u] = T++;
for (int v:E[u]) dfs(v, A[u], B[u]);
Exit[u] = T;
}
struct Block {
Block(int L, int R, const vector<ll>&A, const vector<ll>&B) : U(2*(R-L)), L(L), R(R), off(0), cur(0) {
for (int i = L; i < R; ++i) W.push_back({{B[i], A[i]*B[i]}, i});
for (int i = L; i < R; ++i) if (A[i] < 0 || B[i] < 0) W.push_back({{-B[i], -A[i]*B[i]}, i});
sort(W.begin(),W.end());
build();
}
void build() {
U.clear();
for (auto &w:W) U.insert_line(w.x.x, w.x.y);
cur = U.advance(0LL).x;
}
void add(int l, int r, ll x) {
if (l >= R || r <= L) return;
else if (l <= L && r >= R) {
cur = U.advance(x).x;
off += x;
} else {
for (auto &w:W) {
w.x.y += w.x.x * off;
if (in(l, w.y, r)) {
w.x.y += w.x.x * x;
}
}
off = 0;
build();
}
}
ll get(int l, int r) {
if (l >= R || r <= L) return numeric_limits<ll>::min();
else if (l <= L && r >= R) return cur;
else {
ll ans = numeric_limits<ll>::min();
for (auto &w:W) {
if (in(l, w.y, r)) {
ans = max(ans, w.x.x * off + w.x.y);
}
}
return ans;
}
}
LinearEnvelope::Upper<ll> U;
vector<pair<pair<ll,ll>,int>> W;
int L, R;
ll off, cur;
};
void solve(istream& cin, ostream& cout) {
TOTAL = 0;
int N, Q; cin >> N >> Q;
E.resize(N);
A.resize(N);
B.resize(N);
RA.resize(N);
RB.resize(N);
Enter.resize(N);
Exit.resize(N);
for (int i = 1; i < N; ++i) {
int p; cin >> p; --p;
E[p].push_back(i);
}
cin >> A >> B;
T = 0;
dfs(0, 0, 0);
for (int i = 0; i < N; ++i) {
RA[Enter[i]] = A[i];
RB[Enter[i]] = B[i];
}
int BS = max(1,(int)sqrt(N/6));
vector<Block> D;
D.reserve(1+(N-1)/BS);
for (int i = 0; i < N; i+=BS) D.emplace_back(i, min(i+BS,N), RA, RB);
ll diff = 0;
for (int q = 0; q < Q; ++q) {
int t,v; cin >> t >> v;
--v;
if (t == 1) {
ll x; cin >> x;
for (Block&b:D) b.add(Enter[v],Exit[v],x);
} else {
ll ans = numeric_limits<ll>::min();
for (Block&b:D) ans = max(ans, b.get(Enter[v],Exit[v]));
cout << ans << '\n';
}
}
}
};
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
RPPS solver;
std::istream& in(std::cin);
std::ostream& out(std::cout);
solver.solve(in, out);
return 0;
}
Tutorial is loading...
Code
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define x first
#define y second
typedef long long ll;
template<typename T,typename F>T bsl(T l,T h,const F&f){T r=-1,m;while(l<=h){m=(l+h)/2;if(f(m)){h=m-1;r=m;}else{l=m+1;}}return r;}
/** Successive shortest paths algorithm. Runs in O(maxFlow * (|E| + sumCosts)). */
template<typename Cap = int, typename Cost = int>
struct SSPA {
struct Edge{
Cost c; Cap f; int to, rev;
Edge(int _to, Cost _c, Cap _f, int _rev):c(_c), f(_f), to(_to), rev(_rev){}
};
int N, source, sink;
vector<vector<Edge>> G;
SSPA(int N, int source, int sink): N(N), source(source), sink(sink), G(N) {}
void addEdge(int a, int b, Cap cap, Cost cost) {
assert(cap>=0);
assert(a>=0&&a<N&&b>=0&&b<N);
if(a==b){assert(cost>=0); return;}
G[a].emplace_back(b, cost, cap, G[b].size());
G[b].emplace_back(a, -cost, 0, G[a].size()-1);
}
pair<Cap, Cost> minCostMaxFlow() {
/* Vertex potentials. These are maintained so that all edges with non-zero
* residual have non-negative length. Thus, Dijkstra can be used instead of
* Bellman-Ford in each step of the algorithm. */
vector<Cost> Pi(N, 0);
Cost infty = std::numeric_limits<Cost>::max();
Cap totFlow = 0;
Cost totCost = 0;
while (true) {
vector<Cost> D(N, infty);
vector<int> Prev(N, -1);
D[source] = 0;
vector<vector<int>> Q{{source}};
for (int i = 0; i < Q.size(); ++i) {
for (int j = 0; j < Q[i].size(); ++j) {
int u = Q[i][j];
if (D[u] < i) continue;
for (auto &e: G[u]) {
if (e.f > 0) {
Cost c = D[u] + e.c;
if (D[e.to] > c) {
D[e.to] = c;
while (c >= Q.size()) Q.emplace_back();
Q[c].push_back(e.to);
Prev[e.to] = u;
}
}
}
}
}
// if sink is unreachable, flow is optimal
if (D[sink] == infty) break;
// reconstruct some shortest path
int v = sink;
vector<int> Path;
while (v != -1) { Path.push_back(v); v = Prev[v]; }
reverse(Path.begin(),Path.end());
// found the minimum of the edge residuals along the path
Cap augment = std::numeric_limits<Cap>::max();
int L = Path.size();
for (int i = 0; i < L-1; ++i) {
int u = Path[i], v = Path[i+1];
for (auto&e: G[u]) {
// be careful, there might be multiedges
if (e.to == v && e.f > 0 && D[v] == D[u] + e.c) {
augment = min(augment, e.f);
break;
}
}
}
for (int i = 0; i < L-1; ++i) {
int u = Path[i], v = Path[i+1];
for (auto&e: G[u]) {
if (e.to == v && e.f > 0 && D[v] == D[u] + e.c) {
e.f -= augment;
G[v][e.rev].f += augment;
break;
}
}
}
// store the cost & flow size
Cost cost = Pi[source] - Pi[sink] + D[sink];
totFlow += augment;
totCost += cost * augment;
// remove potentials from costs
for (int i = 0; i < N; ++i) {
for (auto &e: G[i]) {
e.c -= Pi[e.to] - Pi[i];
}
}
// add potentials to costs again
for (int i = 0; i < N; ++i) {
for (auto &e: G[i]) {
e.c += (Pi[e.to] - D[e.to]) - (Pi[i] - D[i]);
}
}
// update potentials based on the results
for (int i = 0; i < N; ++i) Pi[i] -= D[i];
}
return {totFlow,totCost};
}
};
class Stock {
public:
void solve(istream& cin, ostream& cout) {
int N; cin >> N;
vector<int> A(2*N), B(2*N);
for (int i = 0; i < 2*N; ++i) {
cin >> A[i] >> B[i];
}
// find T: O(N log MAX log N)
int T = bsl(0, 1000000000, [&](int t) {
// ( (price at 0) x (-price at t) x (is initial stock) )
vector<pair<pair<int, ll>, bool>> Stocks(2*N);
for (int i = 0; i < 2*N; ++i) {
Stocks[i] = {{B[i], -(A[i]*ll(t) + B[i])}, i<N};
}
sort(Stocks.begin(),Stocks.end());
ll best = 0;
vector<ll> CanHave, Required;
for (int i = 0; i < 2*N; ++i) {
best = max(best, -Stocks[i].x.y);
if (Stocks[i].y) {
CanHave.push_back(best);
} else {
Required.push_back(-Stocks[i].x.y);
}
}
sort(CanHave.begin(),CanHave.end());
sort(Required.begin(),Required.end());
for (int i = 0; i < N; ++i) {
if (CanHave[i] < Required[i]) return false;
}
return true;
});
if (T == -1) {
cout << -1 << endl;
return;
}
vector<pair<pair<int,ll>,int>> Begin(2*N);
vector<pair<ll, int>> End(2*N);
for (int i = 0; i < 2*N; ++i) {
ll end = A[i]*ll(T) + B[i];
// bigger start => process later
// bigger end => process earlier
Begin[i] = {{B[i], -end}, i};
// bigger end => process later
// bigger id => process earlier
End[i] = {end, -i};
}
sort(Begin.begin(),Begin.end());
sort(End.begin(),End.end());
reverse(Begin.begin(),Begin.end());
reverse(End.begin(),End.end());
// SSPA, using O(dijkstra * flow)
SSPA<int,int> G(6*N+2, 6*N, 6*N+1);
for (int i = 0; i < 2*N; ++i) {
if (i != 2*N-1) {
int j = Begin[i].y;
int k = Begin[i+1].y;
G.addEdge(N+j, N+k, N, 0); // perform exchange at t=0
j = -End[i].y;
k = -End[i+1].y;
G.addEdge(3*N+j, 3*N+k, N, 0); // perform exchange at t=T
}
if (Begin[i].y < N) {
int j = Begin[i].y;
G.addEdge(6*N, j, 1, 0); // super source
G.addEdge(j, N+j, 1, 1); // exchange for something at t=0
G.addEdge(j, 3*N+j, 1, 0); // hold until t=T
}
if ((-End[i].y) >= N) {
int j = -End[i].y;
G.addEdge(N+j, 5*N+(j-N), 1, 0); // was kept from t=0
G.addEdge(3*N+j, 5*N+(j-N), 1, 1); // was exchanged at t=T
G.addEdge(5*N+(j-N), 6*N+1, 1, 0); // super sink
}
G.addEdge(N+i, 3*N+i, N, 0); // hold between 0 and T
}
auto res = G.minCostMaxFlow();
assert(res.x == N);
cout << T << ' ' << res.y << '\n';
}
};
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
Stock solver;
std::istream& in(std::cin);
std::ostream& out(std::cout);
solver.solve(in, out);
return 0;
}