codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1175.md (12390B)


      1 Source: https://codeforces.com/blog/entry/67484
      2 
      3 [1175A - From Hero to Zero](/contest/1175/problem/A "Educational Codeforces Round 66 (Rated for Div. 2)")
      4 
      5 Idea: [Roms](/profile/Roms "Master Roms")
      6 
      7 **Tutorial**
      8 
      9 Tutorial is loading...
     10 
     11 **Solution (Roms)**
     12 
     13 ```
     14 #include<bits/stdc++.h>
     15 
     16 using namespace std;
     17 
     18 long long n, k;
     19 
     20 int main(){
     21     int tc;
     22     cin >> tc;
     23     for(int i = 0; i < tc; ++i){
     24     	cin >> n >> k;
     25     	long long res = 0;
     26     	while(n > 0){
     27     	    if(n % k == 0){
     28     	        n /= k;
     29     	        ++res;
     30     	    }
     31     	    else{
     32     	        long long rem = n % k;
     33     	        res += rem;
     34     	        n -= rem;
     35     	    }
     36     	}
     37     	
     38     	cout << res << endl;
     39     }
     40 	return 0;
     41 }
     42 ```
     43 
     44 [1175B - Catch Overflow!](/contest/1175/problem/B "Educational Codeforces Round 66 (Rated for Div. 2)")
     45 
     46 Idea: [awoo](/profile/awoo "Master awoo")
     47 
     48 **Tutorial**
     49 
     50 Tutorial is loading...
     51 
     52 **Solution (PikMike)**
     53 
     54 ```
     55 #include <bits/stdc++.h>
     56 
     57 #define forn(i, n) for(int i = 0; i < int(n); i++) 
     58 
     59 using namespace std;
     60 
     61 const long long INF = 1ll << 32;
     62 
     63 int main(){
     64 	int l;
     65 	cin >> l;
     66 	
     67 	stack<long long> cur;
     68 	cur.push(1);
     69 	
     70 	long long res = 0;
     71 	forn(_, l){
     72 		string t;
     73 		cin >> t;
     74 		if (t == "for"){
     75 			int x;
     76 			cin >> x;
     77 			cur.push(min(INF, cur.top() * x));
     78 		}
     79 		else if (t == "end"){
     80 			cur.pop();
     81 		}
     82 		else{
     83 			res += cur.top();
     84 		}
     85 	}
     86 	
     87 	if (res >= INF)
     88 		cout << "OVERFLOW!!!" << endl;
     89 	else
     90 		cout << res << endl;
     91 }
     92 ```
     93 
     94 [1175C - Electrification](/contest/1175/problem/C "Educational Codeforces Round 66 (Rated for Div. 2)")
     95 
     96 Idea: [adedalic](/profile/adedalic "International Master adedalic")
     97 
     98 **Tutorial**
     99 
    100 Tutorial is loading...
    101 
    102 **Solution (adedalic)**
    103 
    104 ```
    105 #include<bits/stdc++.h>
    106 
    107 using namespace std;
    108 
    109 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    110 #define sz(a) int((a).size())
    111 
    112 int n, k;
    113 vector<int> a;
    114 
    115 inline bool read() {
    116 	if(!(cin >> n >> k))
    117 		return false;
    118 	a.resize(n);
    119 	fore(i, 0, n)
    120 		cin >> a[i];
    121 	return true;
    122 }
    123 
    124 inline void solve() {
    125 	pair<int, int> ans = {int(1e9) + 7, -1};
    126 	fore(i, 0, n - k) {
    127 		int dist = a[i + k] - a[i];
    128 		ans = min(ans, make_pair(dist, a[i] + dist / 2));
    129 	}
    130 	
    131 	cout << ans.second << endl;
    132 }
    133 
    134 int main() {
    135 #ifdef _DEBUG
    136 	freopen("input.txt", "r", stdin);
    137 	int tt = clock();
    138 #endif
    139 	ios_base::sync_with_stdio(false);
    140 	cin.tie(0), cout.tie(0);
    141 	cout << fixed << setprecision(15);
    142 	
    143 	int tc; cin >> tc;
    144 	
    145 	while(tc--) {
    146 	    read();
    147 		solve();
    148 		
    149 #ifdef _DEBUG
    150 		cerr << "TIME = " << clock() - tt << endl;
    151 		tt = clock();
    152 #endif
    153 	}
    154 	return 0;
    155 }
    156 ```
    157 
    158 [1175D - Array Splitting](/contest/1175/problem/D "Educational Codeforces Round 66 (Rated for Div. 2)")
    159 
    160 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    161 
    162 **Tutorial**
    163 
    164 Tutorial is loading...
    165 
    166 **Solution (Roms)**
    167 
    168 ```
    169 #include<bits/stdc++.h>
    170 
    171 using namespace std;
    172 
    173 const int N = 300009;
    174 
    175 int n, k;
    176 int a[N];
    177 
    178 int main(){
    179 	cin >> n >> k;
    180 	for(int i = 0; i < n; ++i)
    181 		cin >> a[i];
    182 	
    183 	long long sum = 0;
    184 	vector <long long> v;
    185 	for(int i = n - 1; i >= 0; --i){
    186 	    sum += a[i];
    187 	    if(i > 0) v.push_back(sum);
    188 	}
    189 	
    190 	long long res = sum;
    191 	
    192 	sort(v.begin(), v.end());
    193 	reverse(v.begin(), v.end());
    194 	
    195 	
    196 	for(int i = 0; i < k - 1; ++i)
    197 	    res += v[i];
    198 	    
    199 	cout << res << endl;
    200 	return 0;
    201 }
    202 ```
    203 
    204 [1175E - Minimal Segment Cover](/contest/1175/problem/E "Educational Codeforces Round 66 (Rated for Div. 2)")
    205 
    206 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    207 
    208 **Tutorial**
    209 
    210 Tutorial is loading...
    211 
    212 **Solution 1 (PikMike)**
    213 
    214 ```
    215 #include <bits/stdc++.h>
    216 
    217 using namespace std;
    218 
    219 #define x first
    220 #define y second
    221 #define forn(i, n) for(int i = 0; i < int(n); i++) 
    222 
    223 const int N = 500 * 1000 + 13;
    224 const int LOGN = 18;
    225 
    226 int n, m;
    227 pair<int, int> a[N], q[N];
    228 
    229 int nxt[N];
    230 int up[LOGN][N];
    231 
    232 int main(){
    233 	scanf("%d%d", &n, &m);
    234 	forn(i, n)
    235 		scanf("%d%d", &a[i].x, &a[i].y);
    236 	forn(i, m)
    237 		scanf("%d%d", &q[i].x, &q[i].y);
    238 	
    239 	sort(a, a + n);
    240 	
    241 	int lst = 0;
    242 	pair<int, int> mx(0, -1);
    243 	forn(i, N){
    244 		while (lst < n && a[lst].x == i){
    245 			mx = max(mx, make_pair(a[lst].y, lst));
    246 			++lst;
    247 		}
    248 		nxt[i] = (mx.x <= i ? -1 : mx.y);
    249 	}
    250 	
    251 	forn(i, n)
    252 		up[0][i] = nxt[a[i].y];
    253 	for (int j = 1; j < LOGN; ++j) forn(i, n){
    254 		if (up[j - 1][i] == -1)
    255 			up[j][i] = -1;
    256 		else
    257 			up[j][i] = up[j - 1][up[j - 1][i]];
    258 	}
    259 	
    260 	forn(i, m){
    261 		int x = nxt[q[i].x];
    262 		
    263 		if (x == -1){
    264 			puts("-1");
    265 			continue;
    266 		}
    267 		
    268 		int res = 1;
    269 		for (int j = LOGN - 1; j >= 0; --j){
    270 			int y = up[j][x];
    271 			if (y == -1)
    272 				continue;
    273 			if (a[y].y < q[i].y){
    274 				res += (1 << j);
    275 				x = y;
    276 			}
    277 		}
    278 		
    279 		if (a[x].y >= q[i].y)
    280 			printf("%d\n", res);
    281 		else if (up[0][x] == -1)
    282 			puts("-1");
    283 		else
    284 			printf("%d\n", res + 1);
    285 	}
    286 }
    287 ```
    288 
    289 **Solution 2 (PikMike)**
    290 
    291 ```
    292 #include <bits/stdc++.h>
    293 
    294 using namespace std;
    295 
    296 #define x first
    297 #define y second
    298 #define forn(i, n) for(int i = 0; i < int(n); i++) 
    299 
    300 const int N = 500 * 1000 + 13;
    301 
    302 int n, m;
    303 pair<int, int> a[N], q[N];
    304 
    305 int nxt[N];
    306 int ans[N];
    307 
    308 pair<int, int> p[N];
    309 
    310 pair<int, int> get(int x, int r){
    311 	if (x == -1)
    312 		return make_pair(-1, -1);
    313 	if (a[x].y >= r)
    314 		return make_pair(x, 0);
    315 	auto res = get(p[x].x, r);
    316 	if (res.x == -1)
    317 		p[x] = make_pair(-1, -1);
    318 	else
    319 		p[x] = make_pair(res.x, p[x].y + res.y);
    320 	return p[x];
    321 }
    322 
    323 int main(){
    324 	scanf("%d%d", &n, &m);
    325 	forn(i, n)
    326 		scanf("%d%d", &a[i].x, &a[i].y);
    327 	forn(i, m)
    328 		scanf("%d%d", &q[i].x, &q[i].y);
    329 	sort(a, a + n);
    330 	
    331 	int lst = 0;
    332 	pair<int, int> mx(0, -1);
    333 	forn(i, N){
    334 		while (lst < n && a[lst].x == i){
    335 			mx = max(mx, make_pair(a[lst].y, lst));
    336 			++lst;
    337 		}
    338 		nxt[i] = (mx.x <= i ? -1 : mx.y);
    339 	}
    340 	
    341 	vector<int> perm(m);
    342 	iota(perm.begin(), perm.end(), 0);
    343 	sort(perm.begin(), perm.end(), [](int a, int b){
    344 		return q[a].y < q[b].y;
    345 	});
    346 	
    347 	forn(i, n)
    348 		p[i] = make_pair(nxt[a[i].y], nxt[a[i].y] == -1 ? -1 : 1);
    349 	
    350 	for (auto i : perm){
    351 		int x = nxt[q[i].x];
    352 		auto res = get(x, q[i].y).y;
    353 		ans[i] = (res == -1 ? -1 : res + 1);
    354 	}
    355 	
    356 	forn(i, m)
    357 		printf("%d\n", ans[i]);
    358 }
    359 ```
    360 
    361 [1175F - The Number of Subpermutations](/contest/1175/problem/F "Educational Codeforces Round 66 (Rated for Div. 2)")
    362 
    363 Idea: [Roms](/profile/Roms "Master Roms")
    364 
    365 **Tutorial**
    366 
    367 Tutorial is loading...
    368 
    369 **Solution (Roms)**
    370 
    371 ```
    372 #include <bits/stdc++.h>
    373 
    374 using namespace std;
    375 
    376 typedef pair<long long, long long> pt;
    377 
    378 const int N = int(3e5) + 99;
    379 const pt zero = make_pair(0, 0);
    380 
    381 int n;
    382 int a[N];
    383 pt hsh[N], sumHsh[N];
    384 
    385 void upd(pt &a, pt b){
    386     a.first ^= b.first;
    387     a.second ^= b.second;
    388 }
    389 
    390 int calc(int pos){
    391 	set <int> sl, sr;
    392 	set<pt> s;
    393 	int r = pos + 1, l = pos - 1;
    394 	pt curr = hsh[0], curl = zero;
    395 	s.insert(zero);
    396 	sr.insert(0), sl.insert(0);
    397 	
    398 	int res = 0;	
    399 	while(r < n && !sr.count(a[r])){
    400 		sr.insert(a[r]);
    401 		upd(curr, hsh[a[r]]);
    402 		++r;
    403 
    404 		while(l >= 0 && !sl.count(a[l]) && a[l] < *sr.rbegin()){
    405 			sl.insert(a[l]);
    406 			upd(curl, hsh[a[l]]);
    407 			s.insert(curl);
    408 			--l;	
    409 		}
    410 
    411 		pt need = sumHsh[*sr.rbegin()];
    412 		upd(need, curr);
    413 		if(s.count(need)) ++res;
    414 	}	
    415 
    416 	return res;
    417 }	
    418 
    419 int main() {
    420     long long x = 0;
    421 	cin >> n;
    422 	for(int i = 0; i < n; ++i){
    423 		cin >> a[i];
    424 		--a[i];	
    425 		x ^= a[i];
    426 	}
    427 	
    428 	
    429 	mt19937_64 rnd(time(NULL));
    430 	for(int i = 0; i < N; ++i){
    431 		hsh[i].first = rnd() ^ x;
    432 		hsh[i].second = rnd() ^ x;
    433 		sumHsh[i] = hsh[i];
    434 		if(i > 0) upd(sumHsh[i], sumHsh[i - 1]);
    435 	}
    436 	
    437 	int res = 0;
    438 		
    439 	for(int tc = 0; tc < 2; ++tc){
    440 		for(int i = 0; i < n; ++i)
    441 			if(a[i] == 0)
    442 				res += calc(i) + (tc == 0);
    443 		reverse(a, a + n);
    444 	}
    445 	cout << res << endl;
    446 
    447 	return 0;
    448 }
    449 ```
    450 
    451 [1175G - Yet Another Partiton Problem](/contest/1175/problem/G "Educational Codeforces Round 66 (Rated for Div. 2)")
    452 
    453 Idea: [adedalic](/profile/adedalic "International Master adedalic")
    454 
    455 **Tutorial**
    456 
    457 Tutorial is loading...
    458 
    459 **Solution (adedalic)**
    460 
    461 ```
    462 #include<bits/stdc++.h>
    463 
    464 using namespace std;
    465 
    466 #define fore(i, l, r) for(int i = int(l); i < int(r); i++)
    467 #define sz(a) (int)((a).size())
    468 
    469 #define x first
    470 #define y second
    471 
    472 typedef long long li;
    473 typedef pair<li, li> pt;
    474 
    475 const int INF = int(1e9);
    476 const li INF64 = li(1e9);
    477 
    478 pt operator -(const pt &a, const pt &b) {
    479     return {a.x - b.x, a.y - b.y};
    480 }
    481 li operator *(const pt &a, const pt &b) {
    482     return a.x * b.x + a.y * b.y;
    483 }
    484 li operator %(const pt &a, const pt &b) {
    485     return a.x * b.y - a.y * b.x;
    486 }
    487 pt rotate(const pt &p) {
    488     return {-p.y, p.x};
    489 }
    490 
    491 struct LinearHull {
    492     deque<pt> pts, vecs;
    493 
    494     void addRight(const pt &l) {
    495         while(!vecs.empty() && vecs.back() * (l - pts.back()) < 0) {
    496             vecs.pop_back();
    497             pts.pop_back();
    498         }
    499         if(!pts.empty())
    500             vecs.push_back(rotate(l - pts.back()));
    501         pts.push_back(l);
    502     }
    503     void addLeft(const pt &l) {
    504         while(!vecs.empty() && vecs.front() * (l - pts.front()) < 0) {
    505             vecs.pop_front();
    506             pts.pop_front();
    507         }
    508         if(!pts.empty())
    509             vecs.push_front(rotate(pts.front() - l));
    510         pts.push_front(l);
    511     }
    512 
    513     li getMin(const pt &x) {
    514         auto it = lower_bound(vecs.begin(), vecs.end(), x, [](const pt &a, const pt &b) {
    515             return a % b > 0;
    516         });
    517         return x * pts[it - vecs.begin()];
    518     }
    519 };
    520 
    521 typedef unique_ptr<LinearHull> pHull;
    522 
    523 void mergeHulls(pHull &a, pHull &b) {
    524     if(sz(b->pts) >= sz(a->pts)) {
    525         for(auto &p : a->pts)
    526             b->addRight(p);
    527     } else {
    528         for(auto it = b->pts.rbegin(); it != b->pts.rend(); it++)
    529             a->addLeft(*it);
    530         swap(a, b);
    531     }
    532 }
    533 
    534 const int M = 1000 * 1000 + 555;
    535 int szn = 0;
    536 struct node {
    537     pt line;
    538     node *l, *r;
    539 
    540     node() : line(), l(nullptr), r(nullptr) {}
    541     node(pt line, node *l, node *r) : line(move(line)), l(l), r(r) {}
    542 } nodes[M];
    543 
    544 typedef node* tree;
    545 
    546 tree getNode(const pt &line, tree l, tree r) {
    547     assert(szn < M);
    548     nodes[szn] = node(line, l, r);
    549     return &nodes[szn++];
    550 }
    551 tree copy(tree v) {
    552     if(v == nullptr) return v;
    553     return getNode(v->line, v->l, v->r);
    554 }
    555 
    556 li f(const pt &line, int x) {
    557     return line * pt{x, 1};
    558 }
    559 
    560 tree addLine(tree v, int l, int r, pt line) {
    561     if(!v)
    562         return getNode(line, nullptr, nullptr);
    563     int mid = (l + r) >> 1;
    564     bool lf = f(line, l) < f(v->line, l);
    565     bool md = f(line, mid) < f(v->line, mid);
    566 
    567     if(md)
    568         swap(v->line, line);
    569 
    570     if(l + 1 == r)
    571         return v;
    572     else if(lf != md)
    573         v->l = addLine(copy(v->l), l, mid, line);
    574     else
    575         v->r = addLine(copy(v->r), mid, r, line);
    576     return v;
    577 }
    578 
    579 li getMin(tree v, int l, int r, int x) {
    580     if(!v) return INF64;
    581     if(l + 1 == r)
    582         return f(v->line, x);
    583     int mid = (l + r) >> 1;
    584 
    585     if(x < mid)
    586         return min(f(v->line, x), getMin(v->l, l, mid, x));
    587     else
    588         return min(f(v->line, x), getMin(v->r, mid, r, x));
    589 }
    590 
    591 int n, k;
    592 vector<li> a;
    593 
    594 inline bool read() {
    595     if(!(cin >> n >> k))
    596         return false;
    597     a.resize(n);
    598 
    599     fore(i, 0, n)
    600         cin >> a[i];
    601     return true;
    602 }
    603 
    604 struct state {
    605     int pos;
    606     pHull hull;
    607     tree v;
    608 
    609     state() : pos(-1), hull(nullptr), v(nullptr) {}
    610 };
    611 
    612 vector<li> d[2];
    613 
    614 inline void solve() {
    615     int maxn = (int)*max_element(a.begin(), a.end()) + 3;
    616     fore(k, 0, 2)
    617         d[k].resize(n + 1, INF64);
    618 
    619     d[0][0] = 0;
    620     fore(_k, 1, k + 1) {
    621         szn = 0;
    622 
    623         int ck = _k & 1;
    624         int nk = ck ^ 1;
    625 
    626         vector< state > st;
    627 
    628         fore(i, 0, sz(d[ck])) {
    629             d[ck][i] = INF64;
    630             if(!st.empty())
    631                 d[ck][i] = getMin(st.back().v, 0, maxn, i);
    632 
    633             if(i >= sz(a))
    634                 continue;
    635 
    636             state curVal;
    637             curVal.pos = i;
    638             curVal.hull = make_unique<LinearHull>();
    639             curVal.hull->addRight({-i, d[nk][i]});
    640             curVal.v = nullptr;
    641 
    642             while(!st.empty() && a[st.back().pos] < a[i]) {
    643                 mergeHulls(st.back().hull, curVal.hull);
    644                 st.pop_back();
    645             }
    646             if(!st.empty())
    647                 curVal.v = st.back().v;
    648 
    649             li val = curVal.hull->getMin({a[i], 1});
    650             curVal.v = addLine(copy(curVal.v), 0, maxn, {a[i], val});
    651 
    652             st.push_back(move(curVal));
    653         }
    654     }
    655     cout << d[k & 1][n] << endl;
    656 }
    657 
    658 int main() {
    659 #ifdef _DEBUG
    660     freopen("input.txt", "r", stdin);
    661     int tt = clock();
    662 #endif
    663     ios_base::sync_with_stdio(false);
    664     cin.tie(0), cout.tie(0);
    665     cout << fixed << setprecision(15);
    666 
    667     if(read()) {
    668         solve();
    669 
    670 #ifdef _DEBUG
    671         cerr << "TIME = " << clock() - tt << endl;
    672         tt = clock();
    673 #endif
    674     }
    675     return 0;
    676 }
    677 ```