이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,e) for (int i = s; i <= e; ++i)
#define rrep(i,s,e) for (int i = s; i >= e; --i)
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define len(a) (int)a.size()
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<double> vd;
typedef vector<string> vs;
typedef vector<ll> vll;
const int mx = 3e5;
int ans[mx+1], ft[mx+1];
vector<vi> events;
//O(n log n) easily achievable with merge-sort???
namespace BIT {
void upd (int x, int id) {
for (;id<=mx;id+=id&(-id)) ft[id] += x;
}
int qry (int id) {
int res = 0;
for (;id;id-=id&(-id)) res += ft[id];
return res;
}
}
//important part begins:
void cdq (int l, int r) {
if (l==r) return;
int mid = (l+r)/2;
cdq (l, mid);
cdq (mid+1, r);
//sort in increasing order of x use BIT afterwards clear BIT
//remember that ys are inverted in events
sort(events.begin()+l, events.begin()+r+1);
vii undo;
rep (i,l,r) {
int y = events[i][1], id = events[i][2], delt = events[i][3], t = events[i][4];
if (t>mid) ans[id] += BIT::qry(y);
else {
BIT::upd(delt,y);
undo.pb({delt,y});
}
}
for (ii el : undo) BIT::upd(-el.fi, el.se);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n, q; cin >> n >> q;
bool b[n+1];
string s; cin >> s;
set<int> st;
st.insert(0);
st.insert(n+1);
rep (i,1,n) {
b[i] = s[i-1]-'0';
if (!b[i]) st.insert(i);
}
vi get;
rep (i,1,q) {
string tp; cin >> tp;
int t = len(events);
if (tp[0]=='t') {
int u; cin >> u;
int prv = *--st.lower_bound(u)+1, nxt = *st.upper_bound(u)-1, c = 2*b[u]-1;
events.pb({prv,u,0,c*i,t++});
if (u+1<=mx)
events.pb({u+1,u,0,-c*i,t++});
if (nxt+1<=mx)
events.pb({prv,(nxt+1),0,-c*i,t++});
if (max(u+1,nxt+1)<=mx)
events.pb({u+1,(nxt+1),0,c*i,t++});
if (b[u]) st.insert(u);
else st.erase(u);
b[u] ^= 1;
}
else {
int x, y; cin >> x >> y;
--y;
get.pb(i);
if (*st.lower_bound(x)>y) ans[i] += i;
events.pb({x,y,i,0,t++});
}
}
cdq(0,len(events)-1);
for (int el : get) cout << ans[el] << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |