제출 #962895

#제출 시각아이디문제언어결과실행 시간메모리
962895hariaakas646Election (BOI18_election)C++14
100 / 100
431 ms36436 KiB
#include <bits/stdc++.h> using namespace std; #define scd(t) scanf("%d", &t) #define sclld(t) scanf("%lld", &t) #define forr(i, j, k) for (int i = j; i < k; i++) #define frange(i, j) forr(i, 0, j) #define all(cont) cont.begin(), cont.end() #define mp make_pair #define pb push_back #define f first #define s second typedef long long int lli; typedef pair<int, int> pii; typedef vector<int> vi; typedef vector<bool> vb; typedef vector<lli> vll; typedef vector<string> vs; typedef vector<pii> vii; typedef vector<vi> vvi; typedef map<int, int> mpii; typedef set<int> seti; typedef multiset<int> mseti; typedef long double ld; void usaco() { freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin); // freopen("problem.out", "w", stdout); } struct Data { int tot = 0; int mi = 0; int mil = 0; int mir = 0; }; template <class T> struct SegTree { int size = 1, n; vector<T> segtree; vector<T> vec; T def; // Assign a value void init(int l, T defv) { n = l; def = defv; while (size < n) size *= 2; segtree.assign(2 * size, def); vec.assign(size, def); } T operation(T x, T y) { T out; out.tot = x.tot + y.tot; out.mil = x.mil; out.mil = min(out.mil, x.tot+y.mil); out.mir = y.mir; out.mir = min(out.mir, x.mir + y.tot); // out.mi = min(x.mi, y.mi); // out.mi = min(out.mi, x.mir + y.mil); out.mi = min(min(x.mi+y.tot, y.mi+x.tot), x.mil + y.mir); return out; } void recalculate(int x) { segtree[x] = operation(segtree[2 * x + 1], segtree[2 * x + 2]); } void build(int x, int l, int r) { if (l == r) { segtree[x] = vec[l]; return; } int mid = (l + r) / 2; build(2 * x + 1, l, mid); build(2 * x + 2, mid + 1, r); recalculate(x); } void build() { build(0, 0, size - 1); } void set(int id, T val) { vec[id] = val; } void update(int x, int l, int r, int id, T val) { if (l == r) { segtree[x] = val; return; } int mid = (l + r) / 2; if (id <= mid) { update(2 * x + 1, l, mid, id, val); } else { update(2 * x + 2, mid + 1, r, id, val); } recalculate(x); } void update(int id, T val) { update(0, 0, size - 1, id, val); } T query(int x, int l, int r, int lx, int rx) { if (lx > r || rx < l) { return def; } if (lx <= l && r <= rx) { return segtree[x]; } int mid = (l + r) / 2; T v1 = query(2 * x + 1, l, mid, lx, rx); T v2 = query(2 * x + 2, mid + 1, r, lx, rx); return operation(v1, v2); } T query(int lx, int rx) { return query(0, 0, size - 1, lx, rx); } }; int main() { // usaco(); int n; scd(n); string str; cin >> str; SegTree<Data> segtree; Data tmp; segtree.init(n, tmp); frange(i, n) { if(str[i] == 'C') { tmp.tot = 1; tmp.mi = tmp.mil = tmp.mir = 0; segtree.set(i, tmp); } else { tmp.tot = tmp.mi = tmp.mil = tmp.mir = -1; segtree.set(i, tmp); } } segtree.build(); int q;scd(q); frange(_, q) { int l, r; scd(l); scd(r); l--; r--; printf("%d\n", -segtree.query(l, r).mi); } }

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

election.cpp: In function 'void usaco()':
election.cpp:30:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     freopen("/media/hariaakash646/785EF1075EF0BF46/CompetitiveProgramming/input.in", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
election.cpp: In function 'int main()':
election.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
election.cpp:153:5: note: in expansion of macro 'scd'
  153 |     scd(n);
      |     ^~~
election.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
election.cpp:175:11: note: in expansion of macro 'scd'
  175 |     int q;scd(q);
      |           ^~~
election.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
election.cpp:179:9: note: in expansion of macro 'scd'
  179 |         scd(l);
      |         ^~~
election.cpp:5:21: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    5 | #define scd(t) scanf("%d", &t)
      |                ~~~~~^~~~~~~~~~
election.cpp:180:9: note: in expansion of macro 'scd'
  180 |         scd(r);
      |         ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...