CooloTran's blog

By CooloTran, history, 6 weeks ago, In English

Problem: https://codeforces.cc/problemset/problem/52/C

Here is the link to my solution for 52C: https://codeforces.cc/contest/52/submission/129151622

#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define _pb pop_back
#define _pf pop_front
#define lb lower_bound
#define ub upper_bound
#define mtp make_tuple
#define ll long long
#define ull unsigned long long
#define ldb long double
#define db double
#define str string
#define pi pair<int, int>
#define pll pair<ll, ll>
#define vi vector<int>
#define vll vector<ll>
#define vpi vector<pi>
#define vpll vector<pll>
#define gcd __gcd
#define lcm __lcm
#define __builtin_popcount __builtin_popcountll
#define __builtin_clz __builtin_clzll
#define __builtin_ctz __builtin_ctzll
#define DB1(x) cerr << "DB1 >>" << (#x) << ": " << (x) << '\n'
#define DB2(x, l, r) cerr << "DB2 >>" << (#x) << ": "; for (int (i) = (l); (i) <= (r); ++(i)) cerr << (x)[(i)] << ' '; cerr << '\n'
#define file "TEST"
mt19937_64 rd(time(0));
ll rand(ll l, ll r) { return uniform_int_distribution<ll>(l, r)(rd); }
const ll oo = (ll)1e15;
const int N = (int)2e5 + 5;
const int T = 8e5 + 5;
int n, m;
int a[N];
ll t[T], lazy[T];
void build(int no, int l, int r) {
	int mid = l + (r - l) / 2;
	if (l == r) {
		t[no] = a[l];
		return;
	}
	build(no * 2, l, mid);
	build(no * 2 + 1, mid + 1, r);
	t[no] = min(t[no * 2], t[no * 2 + 1]);
}
void upd(int no, int l, int r, int ql, int qr, int v) {
	int mid = l + (r - l) / 2;
	if (lazy[no] != oo) {
		t[no] += lazy[no];
		if (l != r) {
			if (lazy[no * 2] == oo)
				lazy[no * 2] = 0;
			if (lazy[no * 2 + 1] == oo)
				lazy[no * 2 + 1] = 0;
			lazy[no * 2] += lazy[no], lazy[no * 2 + 1] += lazy[no]; 
		}
		lazy[no] = oo;
	}
	if (l > qr || r < ql)
		return;
	if (ql <= l && r <= qr) {
		// cerr << l << ' ' << r << " : " << t[no] << '\n';
		t[no] += v;
		// cerr << l << ' ' << r << " : " << t[no] << '\n';
		if (l != r) {
			if (lazy[no * 2] == oo)
				lazy[no * 2] = 0;
			if (lazy[no * 2 + 1] == oo)
				lazy[no * 2 + 1] = 0;
			lazy[no * 2] += v, lazy[no * 2 + 1] += v;
		}
		return;
	}
	upd(no * 2, l, mid, ql, qr, v);
	upd(no * 2 + 1, mid + 1, r, ql, qr, v);
	t[no] = min(t[no * 2], t[no * 2 + 1]);
}
ll get(int no, int l, int r, int ql, int qr) {
	int mid = l + (r - l) / 2;
	if (lazy[no] != oo) {
		t[no] += lazy[no];
		if (l != r) {
			if (lazy[no * 2] == oo)
				lazy[no * 2] = 0;
			if (lazy[no * 2 + 1] == oo)
				lazy[no * 2 + 1] = 0;
			lazy[no * 2] += lazy[no], lazy[no * 2 + 1] += lazy[no]; 
		}
		lazy[no] = oo;
	}
	if (r < ql || l > qr)
		return oo;
	if (ql <= l && r <= qr)
		return t[no];
	return min({get(no * 2, l, mid, ql, qr), get(no * 2 + 1, mid + 1, r, ql, qr)});
}
vi stringtoint(str TMP) {
	vi rs;
	rs.pb(0);
	bool ok = 1;
	for (int i = 0; i < TMP.size(); ++i)
		if (TMP[i] == ' ')
			rs.pb(0);
		else if (TMP[i] >= '0' && TMP[i] <= '9') rs.back() = rs.back() * 10 + ((int)TMP[i] - '0');
		else if (TMP[i] == '-')
			ok = 0;
	if (!ok)
		rs.back() *= -1;
	return rs;
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    // freopen(file".inp", "r", stdin);
    // freopen(file".out", "w", stdout);
    cin >> n;
    for (int i = 0; i < n; ++i)
    	cin >> a[i];
    for (int i = 1; i < T - 5; ++i)
    	lazy[i] = oo;
    build(1, 0, n - 1);
    cin >> m;
    while (m--) {
    	str TMP;
    	fflush(stdin);
    	getline(cin, TMP);
    	vi VA = stringtoint(TMP);
    	// DB1(TMP);
    	// DB1(VA.size());
    	if (VA.size() == 2) {
    		int L = VA.front(), R = VA.back();
    		int L1 = L, R1 = R, L2 = L, R2 = R;
    		if (R < L)
    			R1 = n - 1, L2 = 0;
    		cout << min({get(1, 0, n - 1, L1, R1), get(1, 0, n - 1, L2, R2)}) << '\n';
    		continue;
    	}
    	// for (auto j : VA)
    	// 	DB1(j);
    	// cerr << '\n';
    	// DB1(VA.back());
		int L = VA[0], R = VA[1];
		int L1 = L, R1 = R, L2 = 0, R2 = n - 1, v1 = VA.back(), v2 = 0;
		if (R < L)
			R1 = n - 1, L2 = 0, R2 = R, v2 = VA.back();	
		upd(1, 0, n - 1, L1, R1, v1);
		upd(1, 0, n - 1, L2, R2, v2);
		// DB1(L1);
		// DB1(R1);
		// DB1(L2);
		// DB1(R2);
		// return 0;
    }
    // cerr << "Time: " << (ldb)clock() / (ldb)CLOCKS_PER_SEC << '\n';
    return 0;
}

I don't know why does it give me out of bounds error because it runs normally on my computer. I think it's because of the getline function and the fflush(stdin). Can anyone help me :(.

 
 
 
 
  • Vote: I like it
  • -10
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Replacing fflush(stdin) with cin >> ws did the trick! My experience with getline has always required doing that with the whitespace. https://codeforces.cc/contest/52/submission/129165762