Submission #3995748
Source Code Expand
#include <cstdio> #include <iostream> #include <string> #include <vector> #include <sstream> #include <map> #include <set> #include <queue> #include <algorithm> #include <cmath> #include <cstring> #include <typeinfo> #include <numeric> #include <functional> #include <unordered_map> #include <bitset> #include <stack> using namespace std; using ll = long long; using ull = unsigned long long; const ll INF = 1e16; const ll MOD = 1e9 + 7; #define REP(i, n) for(ll i = 0; i < n; i++) class SegmentTree { private: ll n; // 配列の要素数 ll s; // 配列を初期化するときの値 vector<ll> data; // セグメントツリーを持つ配列 public: SegmentTree(ll m, ll t); // mは配列の要素数、tは配列を初期化するときの値 ll operation(ll t1, ll t2); // 二項演算 void update(ll k, ll a); // k番目(0-indexed)の値をaに変更 ll query(ll a, ll b); // [a, b) の値を求める。 ll query(ll a, ll b, ll k, ll l, ll r); // [a, b) の値を求める。 }; SegmentTree::SegmentTree(ll m, ll t){ n = 1; while(n < m) n *= 2; data.assign(2 * n - 1, t); s = t; } ll SegmentTree::operation(ll t1, ll t2){ return min(t1, t2); } void SegmentTree::update(ll k, ll a){ k += n - 1; data[k] = a; while(k > 0){ k = (k - 1) / 2; data[k] = operation(data[k * 2 + 1], data[k * 2 + 2]); } } ll SegmentTree::query(ll a, ll b){ return query(a, b, 0, 0, n); } ll SegmentTree::query(ll a, ll b, ll k, ll l, ll r){ if(r <= a || b <= l) return s; if(a <= l && r <= b){ return data[k]; } else{ ll vl = query(a, b, k * 2 + 1, l, (l + r) / 2); ll vr = query(a, b, k * 2 + 2, (l + r) / 2, r); return operation(vl, vr); } } int main() { ll n; cin >> n; ll cnt = 0; vector<ll> b(n + 1); REP(i, n){ cin >> b[i + 1]; if(b[i + 1] == 0) cnt++; } ll q; cin >> q; vector<vector<ll>> v(n + 1); REP(i, q){ ll l, r; cin >> l >> r; v[l].push_back(r); } SegmentTree st(n + 1, INF); st.update(0, 0); for(ll i = 1; i <= n; i++){ sort(v[i].rbegin(), v[i].rend()); for(auto &r : v[i]){ ll res = st.query(i - 1, r); if(res < st.query(r, r + 1)) st.update(r, res); } ll res = st.query(i - 1, i) + (b[i]? 1 : -1); if(res < st.query(i, i + 1)) st.update(i, res); } cout << st.query(n, n + 1) + cnt << endl; }
Submission Info
Submission Time | |
---|---|
Task | F - NRE |
User | luogu_bot1 |
Language | C++ (GCC 5.4.1) |
Score | 0 |
Code Size | 2687 Byte |
Status | CE |
Compile Error
In file included from /usr/include/c++/5/unordered_map:35:0, from ./Main.cpp:15: /usr/include/c++/5/bits/c++0x_warning.h:32:2: error: #error This file requires compiler and library support for the ISO C++ 2011 standard. This support must be enabled with the -std=c++11 or -std=gnu++11 compiler options. #error This file requires compiler and library support \ ^ ./Main.cpp:21:7: error: expected nested-name-specifier before ‘ll’ using ll = long long; ^ ./Main.cpp:22:7: error: expected nested-name-specifier before ‘ull’ using ull = unsigned long long; ^ ./Main.cpp:24:7: error: ‘ll’ does not name a type const ll INF = 1e16; ^ ./Main.cpp:25:7: error: ‘ll’ does not name a type const ll MOD = 1e9 + 7; ^ ./Main.cpp:38:5: error: ‘ll’ does not name a type ll n; // 配列の要素数 ^ ./Main.cpp:39:5: error: ‘ll’ does not name a type ll s; // 配列を初期化するときの値 ^ ./Main.cpp:40:12: error: ‘ll’ was not declared in this scope vector<ll> data; // セグメン...