This is the editorial for the ETH selection contest, which took place on Saturday 19th October. The problems are in a mashup contest where only the participants have access. To see the problems, first join the group.
UPD: Apparently, you cannot display tutorial for non-public contest. You can download PDF with tutorial. Author's codes are below.
A
#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
using namespace std;
bool is_seq_arithmetic(vector<long long> V) {
sort( V.begin(), V.end() );
long long D = V[1] - V[0];
for (int i=0; i<int(V.size()); ++i) if (V[i] != V[0] + i*D) return false;
return true;
}
int main() {
vector<long long> ages(6);
for (long long &x : ages) cin >> x;
sort( ages.begin(), ages.end() );
vector<long long> possible_differences = { ages[1] - ages[0], ages[2] - ages[1] };
set<long long> answers;
for (long long d : possible_differences) for (long long x : ages) for (long long add : vector<long long>{x-d,x+d}) if (add > 0) {
vector<long long> new_ages = ages;
new_ages.push_back(add);
if (is_seq_arithmetic(new_ages)) answers.insert(add);
}
for (long long x : answers) cout << x << endl;
}
B
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const long long MOD = 1000000007;
int main() {
int N;
cin >> N;
vector<int> S(N);
for (int &s : S) cin >> s;
vector<int> cycle_count(N+1,0);
vector<bool> seen(N,false);
for (int n=0; n<N; ++n) if (!seen[n]) {
seen[n] = true;
int clen = 1, where = n;
while (true) {
where = S[where];
if (seen[where]) break;
seen[where] = true;
++clen;
}
++cycle_count[clen];
}
long long answer = 1;
for (int len=1; len<=N; ++len) if (cycle_count[len]>0) {
int cnt = cycle_count[len];
vector<int> groups;
if (len%2) groups = {1,2,4}; else groups = {4};
vector<long long> dp(cnt+1,0);
dp[0] = 1;
for (int c=1; c<=cnt; ++c) {
for (int g : groups) if (g <= c) {
long long curr = 1;
for (int j=0; j<g-1; ++j) curr = (curr * (c-1-j)) % MOD;
for (int j=0; j<g-1; ++j) curr = (curr * len) % MOD;
dp[c] = (dp[c] + curr * dp[c-g]) % MOD;
}
}
answer = (answer * dp[cnt]) % MOD;
}
cout << answer << endl;
}
C
#include <vector>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
using namespace std;
#define x first
#define y second
typedef std::pair<int,int> pii; typedef long long ll; typedef unsigned int ui;
template <typename T, typename U> std::istream&operator>>(std::istream&i, pair<T,U>&p) {i >> p.x >> p.y; return i;}
template<typename T>std::istream&operator>>(std::istream&i,vector<T>&t) {for(auto&v:t){i>>v;}return i;}
constexpr double PI = 3.14159265358979323846;
template <typename T> struct Segment;
template <typename T> struct Point : public pair<T,T> {
using pair<T,T>::x;
using pair<T,T>::y;
Point(T a=0,T b=0) : pair<T,T>(a,b) {}
Point(const pair<T,T> &p) : pair<T,T>(p.x,p.y) {}
Point(const Point<T>&p) = default;
Point<T>& operator=(const Point<T>&p) = default;
Point<T>& operator-=(const Point<T>&p) { x -= p.x; y -= p.y; return *this; }
Point<T>& operator+=(const Point<T>&p) { x += p.x; y += p.y; return *this; }
Point<T>& operator*=(T f) { x *= f; y *= f; return *this; }
Point<T> operator-(const Point<T>&p) const { Point<T> t(*this); t -= p; return t; }
Point<T> operator+(const Point<T>&p) const { Point<T> t(*this); t += p; return t; }
Point<T> operator*(T f) const { Point<T> t(*this); t *= f; return t; }
T squaredDistance(const Point<T>&o) const { return Segment<T>{*this,o}.squaredLength(); }
long double distance(const Point<T>&o) const { return Segment<T>{*this,o}.length(); }
};
// >0 left turn, <0 right turn, =0 straight
template <typename T> T ccw(const Point<T>&a, const Point<T>&b, const Point<T>&c) { return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x); }
template <typename T> double cosangle(const Point<T>&a, const Point<T> &b, const Point<T> &c) {
return (double)((b.x-a.x)*(c.x-a.x) + (b.y-a.y)*(c.y-a.y)) / a.distance(b) / a.distance(c);
}
template <typename T> double angle(const Point<T>&a, const Point<T> &b, const Point<T> &c) {
return acos(cosangle(a,b,c));
}
template <typename T> int orientation(const Point<T>&a, const Point<T>&b, const Point<T>&c) { auto o = ccw(a,b,c); return (o>1e-6)-(o<-1e-6); }
template <typename T> struct Segment : public pair<Point<T>,Point<T>> {
using pair<Point<T>,Point<T>>::x;
using pair<Point<T>,Point<T>>::y;
explicit Segment(Point<T> a={0,0}, Point<T> b={0,0}) : pair<Point<T>,Point<T>>(a,b) {}
Segment(const Segment<T>&) = default;
Segment<T>& operator=(const Segment<T>&) = default;
inline T dx() const { return x.x - y.x; }
inline T dy() const { return x.y - y.y; }
T squaredLength() const { return dx()*dx()+dy()*dy(); }
long double length() const { return sqrtl(squaredLength()); }
};
template <typename T> struct Polygon : public vector<Point<T>> {
using vector<Point<T>>::vector;
using vector<Point<T>>::at;
using vector<Point<T>>::front;
using vector<Point<T>>::back;
T doubleSignedArea() const {
if (this->empty()) return T(0);
T area = back().x*front().y - back().y*front().x;
for (int i = 0; i < this->size()-1; ++i) area += (at(i).x * at(i+1).y - at(i+1).x * at(i).y);
return area;
}
double circumference() const {
if (this->empty()) return T(0);
T res = back().distance(front());
for (int i = 0; i < this->size()-1; ++i) res += at(i).distance(at(i+1));
return res;
}
};
template <typename T> Polygon<T> convexhull(const vector<Point<T>> &v) {
ui N = (ui)v.size(); vector<Point<T>> w(N+1); int lo = 0;
for (int i = 0; i<N; ++i) if (v[i].y < v[lo].y || (v[i].y == v[lo].y && v[i].x < v[lo].x)) lo = i;
Point<T> o = v[lo];
for (int i = 0; i<N; ++i) w[i+1] = {v[i].x-o.x,v[i].y-o.y};
swap(w[1],w[lo+1]);
sort(w.begin()+2,w.end(),[](Point<T>&a,Point<T>&b) {
if (a.y==0) return b.y != 0 || a.x < b.x;
if (b.y==0) return false;
auto disc = (a.x*b.y-a.y*b.x);
return disc > 0 || (disc == 0 && a.y < b.y);
});
w[0] = w[N];
ui M=1;
for (int i=2;i<=N;++i) {
while(ccw(w[M-1],w[M],w[i]) <= 0) if (M>1) --M; else if (i == N) break; else ++i;
++M; swap(w[M],w[i]);
}
Polygon<T> res(M);
for (int i=0;i<M;++i) res[i] = {w[i+1].x+o.x,w[i+1].y+o.y};
return res;
}
#define next(x) (x==M-1?0:x+1)
class Inexact {
public:
void solve(istream& cin, ostream& cout) {
int N, W, H; cin >> N >> W >> H;
vector<Point<ll>> A(N); cin >> A;
auto Poly = convexhull(A);
if (Poly.size() <= 2) {
cout << 0 << '\n';
return;
}
int M = Poly.size();
vector<Point<double>> DPoly;
for (int i = 0; i < M; ++i) DPoly.emplace_back(Poly[i].x, Poly[i].y);
double ans = PI;
Point<ll> Orig{0,0};
for (int flip = 0; flip < 2; ++flip) {
for (int rot = 0; rot < 4; ++rot) {
int L = 0, R = 0;
for (int i = 0; i < M; ++i) {
if (ccw(Orig, Poly[L], Poly[i]) > 0) L = i;
if (ccw(Orig, Poly[R], Poly[i]) < 0) R = i;
}
ans = min(ans, angle(Orig, Poly[L], Poly[R]));
while (true) {
if (Poly[L].y <= Poly[next(L)].y) break; // no x-intercept
ll num = Poly[L].y * Poly[next(L)].x - Poly[L].x * Poly[next(L)].y;
ll den = Poly[L].y - Poly[next(L)].y;
Point<double> intercept{double(num)/den, 0};
if (intercept.x >= W) break;
// find the right-most point from intercept
while (true) {
if (orientation(intercept, DPoly[R], DPoly[next(R)]) == -1) {
R = next(R);
} else {
break;
}
}
// find whether the angle L/Intercept/R is <= 45 degrees
ans = min(ans, angle(intercept, DPoly[L], DPoly[R]));
L = next(L);
}
swap(W, H);
for (auto &a: Poly) { swap(a.x, a.y); a.y = H - a.y; }
for (auto &a: DPoly) { swap(a.x, a.y); a.y = H - a.y; }
}
for (auto &a: Poly) a.x = W - a.x;
for (auto &a: DPoly) a.x = W - a.x;
reverse(Poly.begin(),Poly.end());
reverse(DPoly.begin(),DPoly.end());
}
cout << fixed << setprecision(10) << ans * 180.0 / PI << '\n';
}
};
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
Inexact solver;
std::istream& in(std::cin);
std::ostream& out(std::cout);
solver.solve(in, out);
return 0;
}
D
#include <bits/stdc++.h>
using namespace std;
int main() {
int n; cin >> n;
vector<int> v;
copy_n(istream_iterator<int>(cin), n, back_inserter(v));
bool ok = false;
for (int i=0; i<n; ++i) {
auto w = v; // make a copy
rotate(w.begin(), w.begin()+i, w.end());
ok |= is_sorted(w.begin(), w.end());
}
cout << (ok ? "Phew\n" : "Lie\n");
}
E
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
scanf("%d", &n);
for(int i=0; i<n; i++) printf("%c", 'a');
for(int i=0; i<n; i++) printf("%c", 'b');
printf("\n");
for(int i=0; i<n-1; i++) printf("%c", 'a');
printf("%c", 'b');
printf("%c", 'a');
for(int i=0; i<n-1; i++) printf("%c", 'b');
printf("\n");
return 0;
}
F
#include <iostream>
using namespace std;
#define int int64_t
struct rectangle {
int x1, y1, x2, y2;
int area() const { return (x2-x1)*(y2-y1); }
};
istream& operator>>(istream& is, rectangle& r) {
return is >> r.x1 >> r.y1 >> r.x2 >> r.y2;
}
signed main() {
int t; cin >> t;
while (t--) {
rectangle a, b;
cin >> a >> b;
int w = min(a.x2, b.x2) - max(a.x1, b.x1);
int h = min(a.y2, b.y2) - max(a.y1, b.y1);
int best = max(a.area(), b.area());
if (w >= 0 && h >= 0) {
best = max(best, rectangle{0, min(a.y1, b.y1),
w, max(a.y2, b.y2)}.area());
best = max(best, rectangle{0, min(a.x1, b.x1),
h, max(a.x2, b.x2)}.area());
}
cout << best << '\n';
}
}
G
/**
* code generated by JHelper
* More info: https://github.com/AlexeyDmitriev/JHelper
* @author majk
*/
#ifndef MAJK_LIB
#define MAJK_LIB
#include <vector>
#include <stack>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <iomanip>
#include <set>
#include <functional>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <cmath>
#include <string>
#include <queue>
#include <array>
#include <bitset>
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, typename U> std::istream&operator>>(std::istream&i, pair<T,U>&p) {i >> p.x >> p.y; return i;}
template<typename T>std::istream&operator>>(std::istream&i,vector<T>&t) {for(auto&v:t){i>>v;}return i;}
template <typename T, typename U> std::ostream&operator<<(std::ostream&o, const pair<T,U>&p) {o << p.x << ' ' << p.y; return o;}
template<typename T>std::ostream&operator<<(std::ostream&o,const vector<T>&t) {if(t.empty())o<<'\n';for(size_t i=0;i<t.size();++i){o<<t[i]<<" \n"[i == t.size()-1];}return o;}
template<typename T> using minheap = priority_queue<T, vector<T>, greater<T>>;
template<typename T> using maxheap = priority_queue<T, vector<T>, less<T>>;
ui logceil(ll x) { return x?8*sizeof(ll)-__builtin_clzll(x):0; }
namespace std { template<typename T,typename U>struct hash<pair<T,U>>{hash<T>t;hash<U>u;size_t operator()(const pair<T,U>&p)const{return t(p.x)^(u(p.y)<<7);}}; }
template<typename T,typename F>T bsh(T l,T h,const F&f){T r=-1,m;while(l<=h){m=(l+h)/2;if(f(m)){l=m+1;r=m;}else{h=m-1;}}return r;}
template<typename F> double bshd(double l,double h,const F&f,double p=1e-9){ui r=3+(ui)log2((h-l)/p);while(r--){double m=(l+h)/2;if(f(m)){l=m;}else{h=m;}}return (l+h)/2;}
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;}
template<typename F> double bsld(double l,double h,const F&f,double p=1e-9){ui r=3+(ui)log2((h-l)/p);while(r--){double m=(l+h)/2;if(f(m)){h=m;}else{l=m;}}return (l+h)/2;}
template<typename T> T gcd(T a,T b) { if (a<b) swap(a,b); return b?gcd(b,a%b):a; }
template<typename T>class vector2:public vector<vector<T>>{public:vector2(){} vector2(size_t a,size_t b,T t=T()):vector<vector<T>>(a,vector<T>(b,t)){}};
template<typename T>class vector3:public vector<vector2<T>>{public:vector3(){} vector3(size_t a,size_t b,size_t c,T t=T()):vector<vector2<T>>(a,vector2<T>(b,c,t)){}};
template<typename T>class vector4:public vector<vector3<T>>{public:vector4(){} vector4(size_t a,size_t b,size_t c,size_t d,T t=T()):vector<vector3<T>>(a,vector3<T>(b,c,d,t)){}};
template<typename T>class vector5:public vector<vector4<T>>{public:vector5(){} vector5(size_t a,size_t b,size_t c,size_t d,size_t e,T t=T()):vector<vector4<T>>(a,vector4<T>(b,c,d,e,t)){}};
#endif
class averaging {
public:
void solve(istream& cin, ostream& cout) {
int N, K; cin >> N >> K;
vector<int> A(N); cin >> A;
int tot = 0;
for (int a: A) tot += a;
vector5<bool> D(N+1, N+1, N+1, 101, 101, false);
D[0][0][0][0][0] = true;
for (int i = 0; i < N; ++i) {
for (int j = 0; j <= i; ++j) {
for (int k = 0; k <= i; ++k) {
for (int l = 0; l <= 100; ++l) {
for (int m = 0; m <= 100; ++m) {
if (D[i][j][k][l][m]) {
D[i+1][j+1][k][l+A[i]][m] = true;
D[i+1][j][k+1][l][m+A[i]] = true;
D[i+1][j][k][l][m] = true;
}
}
}
}
}
}
pii best = {0, 1};
pii diff = {K, 1};
for (int i = 1; i < N; ++i) {
for (int j = 1; j < N; ++j) {
int k = N - i - j;
if (k > 0) {
for (int l = 1; l < 100; ++l) {
for (int m = 1; m < 100; ++m) {
int n = tot - l - m;
if (D[N][i][j][l][m]) {
int den = i*j*k*3;
int num = j*k*l + i*k*m + i*j*n;
int numDiff = abs(num - K*i*j*k*3);
if (numDiff * diff.y < den * diff.x) {
diff = {numDiff, den};
best = {num, den};
} else if (numDiff * diff.y == den * diff.x && num < K*i*j*k*3) {
diff = {numDiff, den};
best = {num, den};
}
}
}
}
}
}
}
int g = gcd(best.x, best.y);
cout << best.x / g << '/' << best.y / g << endl;
}
};
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
averaging solver;
std::istream& in(std::cin);
std::ostream& out(std::cout);
solver.solve(in, out);
return 0;
}
H
#include <algorithm>
#include <iostream>
#include <map>
#include <string>
using namespace std;
int main() {
int W;
cin >> W;
map< string, string > wordlist;
for (int w=0; w<W; ++w) {
string word;
cin >> word;
string sorted_word = word;
sort( sorted_word.begin(), sorted_word.end() );
if (wordlist.count(sorted_word) == 0) wordlist[sorted_word] = word;
}
int Q;
cin >> Q;
for (int q=0; q<Q; ++q) {
string query;
cin >> query;
sort( query.begin(), query.end() );
string answer = "";
for (int subset = 1; subset < (1<<9); ++subset) {
string used = "";
for (int i=0; i<9; ++i) if (subset & 1<<i) used += query[i];
if (wordlist.count(used) == 0) continue;
if (used.size() < answer.size()) continue;
if (used.size() > answer.size()) { answer = wordlist[used]; continue; }
answer = min( answer, wordlist[used] );
}
if (answer == "") answer = "IMPOSSIBLE";
cout << answer << "\n";
}
}
I
#include <vector>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
typedef long long ll;
class die {
public:
void solve(istream& cin, ostream& cout) {
vector<int> A(6); cin >> A;
ll S; cin >> S;
int Q; cin >> Q;
--Q;
S -= A[Q];
vector<int> M(3, 0);
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 6; ++j) {
int k = min(j, 5-j);
if (i != k) {
M[i] |= 1<<(3*A[j]+k-3);
}
}
}
map<int, int> C;
vector<int> D{0};
C[0] = 0;
int cur = 0, id = 0;
while (true) {
int next = (cur&((1<<27)-1))<<3;
for (int i = 0; i < 3; ++i) {
if ((cur & M[i]) != M[i]) next |= 1<<i;
}
cur = next;
D.push_back(cur);
auto it = C.find(cur);
if (it != C.end()) break;
C[cur] = ++id;
}
int prep = C[cur];
int per = id + 1 - C[cur];
if (S > prep) S = (S - prep) % per + prep;
if ((D[S]>>min(Q,5-Q))&1) cout << "ADA" << '\n';
else cout << "BOB" << '\n';
}
};
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
die solver;
std::istream& in(std::cin);
std::ostream& out(std::cout);
solver.solve(in, out);
return 0;
}
J
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int N;
vector< vector<int> > G;
vector<bool> visited;
vector< vector<int> > solution;
bool OK;
bool dfs(int v) {
visited[v] = true;
vector<int> unmatched_children;
for (int x : G[v]) if (!visited[x]) if (!dfs(x)) unmatched_children.push_back(x);
while (unmatched_children.size() >= 2u) {
int a = unmatched_children.back();
unmatched_children.pop_back();
int b = unmatched_children.back();
unmatched_children.pop_back();
solution.push_back( {a,b,v} );
}
if (unmatched_children.empty()) return false;
solution.push_back( {unmatched_children[0], v, -1} );
return true;
}
int main() {
cin >> N;
G.resize(2*N);
int F;
cin >> F;
while (F--) {
int x, y;
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
OK = true;
visited.resize(2*N,false);
for (int n=0; n<2*N; ++n) if (!visited[n]) if (!dfs(n)) OK = false;
cout << (OK ? "POSSIBLE\n" : "IMPOSSIBLE\n");
if (OK) for (auto row : solution) cout << row[0] << " " << row[1] << " " << row[2] << "\n";
}
K
N = int(input())
A, B = map(int, input().split())
best_k = 2000
for i in range(0, N+1):
for j in range(0, N+1):
if (i * A + j * B) % N != 0: continue
if i + j == 0: continue
best_k = min(best_k, i+j)
print(best_k)
L
#include <vector>
#include <iostream>
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>class vector2:public vector<vector<T>>{public:vector2(){} vector2(size_t a,size_t b,T t=T()):vector<vector<T>>(a,vector<T>(b,t)){}};
template <unsigned int N> class Field {
typedef unsigned int ui;
typedef unsigned long long ull;
inline ui pow(ui a, ui p){ui r=1,e=a;while(p){if(p&1){r=((ull)r*e)%N;}e=((ull)e*e)%N;p>>=1;}return r;}
inline ui inv(ui a){return pow(a,N-2);}
public:
inline Field(int x = 0) : v(x) {}
inline Field<N> pow(int p){return (*this)^p; }
inline Field<N> operator^(int p){return {(int)pow(v,(ui)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) {if (v<o.v) 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) { return *this*=inv(o.v); }
inline Field<N> operator+(const Field<N>&o) const {Field<N>r{*this};return r+=o;}
inline Field<N> operator-(const Field<N>&o) const {Field<N>r{*this};return r-=o;}
inline Field<N> operator*(const Field<N>&o) const {Field<N>r{*this};return r*=o;}
inline Field<N> operator/(const Field<N>&o) const {Field<N>r{*this};return r/=o;}
inline Field<N> operator-() {if(v) return {(int)(N-v)}; else return {0};};
inline Field<N>& operator++() { ++v; if (v==N) v=0; return *this; }
inline Field<N> operator++(int) { Field<N>r{*this}; ++*this; return r; }
inline Field<N>& operator--() { --v; if (v==-1) v=N-1; return *this; }
inline Field<N> operator--(int) { Field<N>r{*this}; --*this; return r; }
inline bool operator==(const Field<N>&o) const { return o.v==v; }
inline bool operator!=(const Field<N>&o) const { return o.v!=v; }
inline explicit operator ui() const { return v; }
inline static vector<Field<N>>fact(int t){vector<Field<N>>F(t+1,1);for(int i=2;i<=t;++i){F[i]=F[i-1]*i;}return F;}
inline static vector<Field<N>>invfact(int t){vector<Field<N>>F(t+1,1);Field<N> X{1};for(int i=2;i<=t;++i){X=X*i;}F[t]=1/X;for(int i=t-1;i>=2;--i){F[i]=F[i+1]*(i+1);}return F;}
private: ui v;
};
template<unsigned int N>istream &operator>>(std::istream&is,Field<N>&f){unsigned int v;is>>v;f=v;return is;}
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;}
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<1000000007> FieldMod;
class treequeries {
public:
void solve(istream& cin, ostream& cout) {
int Q; cin >> Q;
vector<FieldMod> B(31, 0);
vector2<int> C(31, 31, 0);
for (int i = 0; i <= 30; ++i) {
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; ++j) C[i][j] = C[i-1][j-1] + C[i-1][j];
}
auto add = [&](int x, FieldMod s) {
int pref = 0, cnt = 0;
for (int i = 30; i >= 0; --i) {
if (x&1<<i) {
for (int j = 0; j <= i; ++j) B[cnt+j] += s * C[i][j];
pref |= 1<<i;
cnt++;
}
}
};
for (int q = 0; q < Q; ++q) {
int t, l, r; cin >> t >> l >> r;
if (t == 0) {
FieldMod X; cin >> X;
add(r, X);
add(l, -X);
} else {
FieldMod ans = 0;
for (int i = 31-r; i < 31-l; ++i) ans += B[i];
cout << ans << '\n';
}
}
}
};
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
treequeries solver;
std::istream& in(std::cin);
std::ostream& out(std::cout);
solver.solve(in, out);
return 0;
}
#youjustwantcontribution lol
I'll just add that it was held at Comenius University in Slovakia too.
Smash that upvote button if it brings GYM contests with editorials.
That's not true. I also want rating!