제출 #1347267

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1347267		hminhat	Uiro (JOI25_uiro)	C++17	21 / 100	916 ms	22016 KiB

Main

/*	
	ROAD TO TST 
*/
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define el "\n"
#define pb push_back
#define all(v) v.begin(), v.end()

#define rep(i, x, y) for(int i = x, _y = y; i <= _y; i++)
#define rev(i, x, y) for(int i = x, _y = y; i >= _y; i--)

void file() {
	#define name "C:\\Users\\hminh\\Desktop\\2026\\AIO\\test"
	if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin);freopen(name".out", "w", stdout);}
	else {
		#undef name
		#define name "test"
		if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin);freopen(name".out", "w", stdout);}
	}
}

const int nmax = 2e5 + 7;

int n, a[nmax], q, pref[nmax], delta[nmax], last[nmax];
int up[18][nmax], ans[nmax], s[nmax];
vector<int> pos;
pii Q[nmax];

int get_min(int l, int r) {
	int k = __lg(r - l + 1);
	return min(up[k][l], up[k][r - (1 << k) + 1]);
}

int main()
{
	file();
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n;
	rep(i, 1, n) cin >> a[i], pref[i] = pref[i - 1] + a[i];
	cin >> q;
	rep(i, 1, q) cin >> Q[i].fi >> Q[i].se, last[i] = Q[i].fi;
	rep(x, 1, 100) {
		rep(i, 1, n) {
			s[i] = s[i - 1];
			if(a[i] == x) {
				pos.pb(i);
				s[i] += a[i];
			}
			up[0][i] = pref[i] - delta[i] * 2 - s[i] * 2;
		}
		if(pos.size() == 0) continue;
		sort(all(pos));
		rep(i, 1, 17) {
			rep(j, 1, n - (1 << i) + 1) {
				up[i][j] = min(up[i - 1][j], up[i - 1][j + (1 << (i - 1))]);
			} 
		}
		rep(i, 1, q) {
			int l = lower_bound(all(pos), last[i]) - pos.begin();
			int r = upper_bound(all(pos), Q[i].se) - pos.begin() - 1;
			int res = r + 1;
			ans[i] += r;
			while(l <= r) {
				int mid = (l + r) >> 1;
				if(get_min(pos[mid], Q[i].se) - pref[Q[i].fi - 1] + delta[last[i]] * 2 + s[pos[mid] - 1] * 2 >= 0) {
					r = mid - 1;
					res = mid;
				}
				else {
					l = mid + 1;
				}
			}
			if(res > 0) last[i] = max(last[i], pos[res - 1]);
			ans[i] -= res - 1;
		}
		int cur = 0;
		rep(i, 1, n) {
			if(a[i] == x) {
				cur += a[i];
			}
			delta[i] += cur;
		}
		pos.clear();
	}
	rep(i, 1, q) cout << ans[i] << el;
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'void file()':
Main.cpp:21:44: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin);freopen(name".out", "w", stdout);}
      |                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:21:76: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin);freopen(name".out", "w", stdout);}
      |                                                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:25:52: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |                 if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin);freopen(name".out", "w", stdout);}
      |                                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:25:84: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |                 if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin);freopen(name".out", "w", stdout);}
      |                                                                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 0 / 3
• Subtask 3: 0 / 5
• Subtask 4: 0 / 7
• Subtask 5: 0 / 15
• Subtask 6: 21 / 21
• Subtask 7: 0 / 29
• Subtask 8: 0 / 20