제출 #530661

#제출 시각아이디문제언어결과실행 시간메모리
530661Killer2501가로등 (APIO19_street_lamps)C++14
0 / 100
159 ms40924 KiB
#include <bits/stdc++.h> #define ll long long #define ld long double #define ull unsigned long long #define pb push_back #define pll pair<ll, ll> #define pii pair<int, int> #define fi first #define se second using namespace std; const int N = 3e5+5; const int M = 250; const int mod = 1e9+7; const ll base = 75; const int inf = 1e9; int m, n, t, b[N], d[N], lab[N], c[N]; int k, a[N], dp[N], lst[N], fe[N]; ll ans, tong; vector<int> adj[N], g[N]; vector<int> vi; string s; bool vis[N]; struct BIT { int n; vector<int> val, fe; BIT(){} void init() { sort(val.begin(), val.end()); val.erase(unique(val.begin(), val.end()), val.end()); fe.resize(val.size(), 0); } void add(int id, int x) { for(; id <= (int)val.size(); id += id & -id)fe[id-1] += x; } void add(int l, int r, int x) { add(lower_bound(val.begin(), val.end(), l) - val.begin()+1, x); add(upper_bound(val.begin(), val.end(), r) - val.begin()+1, -x); } int get(int id) { int res = 0; for(id = upper_bound(val.begin(), val.end(), id) - val.begin(); id; id -= id & id)res += fe[id-1]; return res; } }bit[N]; void fakeget(int l, int r) { for(; l; l -= l & -l) bit[l].val.pb(r); } int get(int l, int r) { int res = 0; for(; l; l -= l & -l)res += bit[l].get(r); return res; } void update(int id, int u, int v, int x) { for(; id <= n; id += id & -id)bit[id].add(u, v, x); } void update(int l, int r, int u, int v, int x) { update(l, u, v, x); update(r+1, u, v, -x); } void sol() { cin >> n >> m >> s; set<int> st; st.insert(0); st.insert(n+1); for(int i = 1; i <= n; i ++) { if(s[i-1] == '0') { st.insert(i); c[i] = 1; } } for(int i = 1; i <= m; i ++) { cin >> s; if(s[0] == 'q') { d[i] = 1; cin >> a[i] >> b[i]; --b[i]; fakeget(a[i], b[i]); } else cin >> a[i]; } for(int i = 1; i <= n; i ++)bit[i].init(); for(int i = 1; i <= m; i ++) { if(d[i]) { ans = get(a[i], b[i]); auto it = st.lower_bound(a[i]); if((*prev(it)) < a[i] && (*it) > b[i])ans += i; cout << ans << '\n'; } else { if(c[a[i]]) { auto it = st.lower_bound(a[i]); update(*prev(it)+1, a[i], a[i], *next(it), -i); st.erase(a[i]); } else { st.insert(a[i]); auto it = st.lower_bound(a[i]); update(*prev(it)+1, a[i], a[i], *next(it), i); } c[a[i]] ^= 1; } } } int main() { cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0); #define task "test" if(fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } int test = 1; //cin >> test; while(test -- > 0)sol(); return 0; }

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

street_lamps.cpp: In function 'int main()':
street_lamps.cpp:133:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  133 |   freopen(task".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
street_lamps.cpp:134:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |   freopen(task".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...