oj.uz

답안 #483063

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
483063 2021-10-27T15:30:48 Z macktvz Election (BOI18_election) C++17
0 / 100
 4 ms 332 KB 
#include <bits/stdc++.h>
#include <cmath>

using namespace std;



template<class T> struct Seg { // comb(ID,b) = b
	const T ID = 1e18; T comb(T a, T b) { return min(a,b); }
	int n; vector<T> seg;
	void init(int _n) { n = _n; seg.assign(2*n,ID); }
	void pull(int p) { seg[p] = comb(seg[2*p],seg[2*p+1]); }
	void upd(int p, T val) { // set val at position p
		seg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); }
	T query(int l, int r) {	// min on interval [l, r]
		T ra = ID, rb = ID;
		for (l += n, r += n+1; l < r; l /= 2, r /= 2) {
			if (l&1) ra = comb(ra,seg[l++]);
			if (r&1) rb = comb(seg[--r],rb);
		}
		return comb(ra,rb);
	}
};

Seg<int> p;
Seg<int> s;

int main() {
    int n; cin >> n;
    int pref[n+1];
    int suff[n+1];
    int v[n];
    p.init(n+1);
    s.init(n+2);
    pref[0] = 0;
    suff[n+1] = 0;
    char a;
    for(int i = 1; i <= n; i++) {
        cin >> a;
        if (a == 'C') v[i] = 1;
        else v[i] = -1;
        pref[i] = pref[i-1] + v[i];
        p.upd(i,pref[i]);
    }
    for(int i = n; i > 0; i--) {
        suff[i] = suff[i+1] + v[i];
        s.upd(i,suff[i]);
    }
    int q; cin >> q;
    int b,c;
    while (q--) {
        cin >> b >> c;
        cout << -min(p.query(b,c)-pref[b-1],s.query(b,c)-suff[c+1]) << endl;
    }

}

Compilation message

election.cpp: In instantiation of 'Seg<int>::Seg()':
election.cpp:25:10:   required from here
election.cpp:9:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
    9 |  const T ID = 1e18; T comb(T a, T b) { return min(a,b); }
      |               ^~~~

Subtask #1
0 / 28.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 54.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 4 ms 332 KB Output isn't correct
2 Halted 0 ms 0 KB -