| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 154955 | 2019-09-25T16:55:39 Z | andrew | Segments (IZhO18_segments) | C++17 | 298 ms | 8140 KB |
#include <bits/stdc++.h>
#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define p_b push_back
#define pll pair<ll,ll>
#define pii pair<int,int>
#define m_p make_pair
#define all(x) x.begin(),x.end()
#define sset ordered_set
#define sqr(x) (x)*(x)
#define pw(x) (1ll << x)
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MAXN = 1123456;
const ll N = 2e5;
const ll inf = 3e18;
int buben = 1000;
mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count());
template <typename T> void vout(T s){cout << s << endl;exit(0);}
pii a[N + 3];
int stn;
int WD[N + 3];
int Wstn;
pii b[N + 3];
int Stn;
bool f_deleted[N + 3], will_deleted[N + 3];
int luk, ruk;
ll Len_Block, Len;
vector <ll> V[501], V1[501];
void clr(){
if(!Len)return;
for(int i = 0; i < Len; i++){
V[i / Len_Block].clear();
V1[i / Len_Block].clear();
}
Len = 0;
Len_Block = 0;
}
void build(int Nt){
Len_Block = 1;
Len = Nt;
while(sqr(Len_Block) < Len)Len_Block++;
for(int i = 0; i < Len; i++){
V[i / Len_Block].p_b(a[i + 1].fi);
V1[i / Len_Block].p_b(a[i + 1].se - a[i + 1].fi + 1);
}
for(int i = 0; i <= (Len - 1) / Len_Block; i++){
sort(all(V[i]));
sort(all(V1[i]));
}
}
int Val;
int V_more(int l, int r){
l--, r--;
int ans = 0;
for(int i = l; i <= r;){
if(i % Len_Block == 0 && i + Len_Block - 1 <= r){
ans += (int)V[i].size() - (lower_bound(all(V[i]), Val) - V[i].begin());
i += Len_Block;
}else{
if(a[i + 1].fi >= Val)ans++;
i++;
}
}
return ans;
}
int V1_more(int l, int r){
l--, r--;
int ans = 0;
for(int i = l; i <= r;){
if(i % Len_Block == 0 && i + Len_Block - 1 <= r){
ans += (int)V1[i].size() - (lower_bound(all(V1[i]), Val) - V1[i].begin());
i += Len_Block;
}else{
if(a[i + 1].se - a[i + 1].fi + 1 >= Val)ans++;
i++;
}
}
return ans;
}
struct qry{
short t;
int a, b, c, Id;
};
qry c[N + 3];
int main(){
ios_base :: sync_with_stdio(0);
cin.tie(0);
int n, t;
cin >> n >> t;
for(int i = 1; i <= n; i++){
cin >> c[i].t;
if(c[i].t == 1){
cin >> c[i].a >> c[i].b;
}else if(c[i].t == 2){
cin >> c[i].a;
}else{
cin >> c[i].a >> c[i].b >> c[i].c;
}
}
int l = 1, last_ans = 0, ans = 0, Le, Ri, L1, R1, L, R, mid, k, i, j;
for(i = 1; i <= n; i++){
if(i % buben == 0){
Wstn = 0;
for(j = i; j <= min(n, i + buben - 1); j++){
if(c[j].t == 2){
will_deleted[c[j].a] = 1;
if(c[j].a <= Stn){
Wstn++;
WD[Wstn] = c[j].a;
}
}
}
clr();
stn = 0;
for(j = 1; j <= Stn; j++)if(!will_deleted[j]){
stn++;
a[stn] = b[j];
}
if(stn){
sort(a + 1, a + stn + 1);
build(stn);
}
l = i;
}
if(c[i].t == 1){
c[i].a ^= t * last_ans;
c[i].b ^= t * last_ans;
if(c[i].a > c[i].b)swap(c[i].a, c[i].b);
Stn++;
c[i].Id = Stn;
b[Stn] = {c[i].a, c[i].b};
}else if(c[i].t == 2){
f_deleted[c[i].a] = 1;
will_deleted[c[i].a] = 1;
}else if(c[i].t == 3){
c[i].a ^= t * last_ans;
c[i].b ^= t * last_ans;
if(c[i].a > c[i].b)swap(c[i].a, c[i].b);
if(c[i].b - c[i].a + 1 < c[i].c){
cout << "0\n";
last_ans = 0;
continue;
}
ans = 0;
k = c[i].c;
for(j = l; j < i; j++)if(c[j].t == 1 && !f_deleted[c[j].Id]){
if(min(c[i].b, c[j].b) - max(c[i].a, c[j].a) + 1 >= c[i].c || c[i].c == 0)ans++;
}
for(j = 1; j <= Wstn; j++)if(!f_deleted[WD[j]]){
if(min(c[i].b, b[WD[j]].se) - max(c[i].a, b[WD[j]].fi) + 1 >= c[i].c || c[i].c == 0)ans++;
}
if(!k)ans += stn;
else{
if(stn){
L = 1, R = stn;
while(L < R){
mid = (L + R) >> 1;
if(a[mid].fi < c[i].a)L = mid + 1; else R = mid;
}
if(a[L].fi < c[i].a)L++;
if(L != 1){
Val = k + c[i].a - 1;
ans += V_more(1, L - 1);
}
Le = L;
L = 1, R = stn;
while(L < R){
mid = (L + R) >> 1;
if(a[mid].fi <= c[i].b - k + 1)L = mid + 1; else R = mid;
}
if(a[L].fi <= c[i].b - k + 1)L++;
if(Le < L){
Val = k;
ans += V1_more(Le, L - 1);
}
}
}
cout << ans << "\n";
last_ans = ans;
}
}
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 380 KB | Output is correct |
| 2 | Correct | 2 ms | 376 KB | Output is correct |
| 3 | Incorrect | 7 ms | 504 KB | Output isn't correct |
| 4 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Runtime error | 298 ms | 8140 KB | Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 108 ms | 2808 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 95 ms | 2740 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 380 KB | Output is correct |
| 2 | Correct | 2 ms | 376 KB | Output is correct |
| 3 | Incorrect | 7 ms | 504 KB | Output isn't correct |
| 4 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 2 ms | 380 KB | Output is correct |
| 2 | Correct | 2 ms | 376 KB | Output is correct |
| 3 | Incorrect | 7 ms | 504 KB | Output isn't correct |
| 4 | Halted | 0 ms | 0 KB | - |