oj.uz

Submission #919010

# Submission time Handle Problem Language Result Execution time Memory
919010 2024-01-31T04:14:26 Z imarn Segments (IZhO18_segments) C++14
7 / 100
 1234 ms 10752 KB 
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define all(x) x.begin(),x.end()
#define vi vector<int>
#define vvi vector<vi>
#define vp vector<pii>
using namespace std;
const int K=1900;
multiset<pair<int,pii>>ms;
vector<pii>bl[120],br[120];
int mn[120]{0},mx[120]{0};
vector<pair<int,pii>>cur,upd;
void build(){
    cur.clear();
    for(auto it : ms)cur.pb({it.s.s-it.s.f+1,{it.s.f,it.s.s}});
    for(int i=0;i<120;i++)bl[i].clear(),br[i].clear(),mx[i]=0,mn[i]=2e9+5;
    sort(all(cur));
    for(int i=0;i<cur.size();i++){
        bl[i/K].pb({cur[i].s.f,cur[i].s.s});
        br[i/K].pb({cur[i].s.s,cur[i].s.f});
        mx[i/K]=max(mx[i/K],cur[i].f);
        mn[i/K]=min(mn[i/K],cur[i].f);
    }for(int i=0;i<120;i++)sort(all(bl[i])),sort(all(br[i]));
    upd.clear();
}
int qr(int k,int le,int re,int ans=0){
    for(int i=0;i<120;i++){
        if(mx[i]<k)continue;
        if(mn[i]>=k){ans+=(int)bl[i].size();continue;}
        for(auto it : bl[i]){
            if(it.s-it.f+1>=k)ans++;
        }
    }
    for(int i=0;i<120;i++){
        if(mx[i]<k)continue;
        if(mn[i]>=k){
            int l=0,r=(int)bl[i].size();
            while(l<r){
                int m=(l+r)>>1;
                if(bl[i][m].f>=re-k+1)r=m;
                else l=m+1;
            }ans-=(int)bl[i].size()-l;continue;
        }
        for(auto it : bl[i]){
            if(it.s-it.f+1>=k&&it.f>=re-k+1)ans--;
        }
    }
    for(int i=0;i<120;i++){
        if(mx[i]<k)continue;
        if(mn[i]>=k){
            int l=-1,r=(int)br[i].size()-1;
            while(l<r){
                int m=(l+r+1)>>1;
                if(br[i][m].f<=le+k-1)l=m;
                else r=m-1;
            }ans-=(l+1);continue;
        }
        for(auto it : br[i]){
            if(it.f-it.s+1>=k&&it.f<=le+k-1)ans--;
        }
    }
    for(auto it : upd){
        if(min(re,it.s.s)-max(le,it.s.f)+1>=k)ans+=it.f;
    }return ans;
}int id=1;
pii seg[200006];
int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);
    int n,t;cin>>n>>t;ll res=0;
    for(int i=0;i<n;i++){
        if(i%K==0)build();
        int o;cin>>o;
        if(o==1){
            int a,b;cin>>a>>b;
            a=(a^(t*res)),b=(b^(t*res));
            if(a>b)swap(a,b);seg[id]={a,b};
            ms.insert({id,{a,b}});id++;
            upd.pb({1,{a,b}});
        }
        if(o==2){
            int c;cin>>c;
            ms.erase(ms.lower_bound({c,{0,0}}));
            upd.pb({-1,{seg[c].f,seg[c].s}});
        }
        if(o==3){
            int a,b,k;cin>>a>>b>>k;
            a=(a^(t*res)),b=(b^(t*res));
            if(a>b)swap(a,b);
            if(b-a+1<k)res=0;
            else res=qr(k,a,b);
            cout<<res<<'\n';
        }

    }
}

Compilation message

segments.cpp: In function 'void build()':
segments.cpp:23:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |     for(int i=0;i<cur.size();i++){
      |                 ~^~~~~~~~~~~
segments.cpp: In function 'int main()':
segments.cpp:81:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   81 |             if(a>b)swap(a,b);seg[id]={a,b};
      |             ^~
segments.cpp:81:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   81 |             if(a>b)swap(a,b);seg[id]={a,b};
      |                              ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 3 ms 344 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 14 ms 856 KB Output is correct
6 Correct 18 ms 856 KB Output is correct
7 Correct 7 ms 600 KB Output is correct
8 Correct 11 ms 912 KB Output is correct
9 Correct 10 ms 856 KB Output is correct
10 Correct 5 ms 860 KB Output is correct
11 Correct 29 ms 860 KB Output is correct
12 Correct 31 ms 860 KB Output is correct
13 Correct 6 ms 856 KB Output is correct
14 Correct 12 ms 856 KB Output is correct
15 Correct 3 ms 600 KB Output is correct
16 Correct 4 ms 600 KB Output is correct
17 Correct 10 ms 600 KB Output is correct
18 Correct 7 ms 1112 KB Output is correct
19 Correct 10 ms 600 KB Output is correct
20 Correct 10 ms 812 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1234 ms 5696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 66 ms 844 KB Output is correct
2 Correct 69 ms 2656 KB Output is correct
3 Correct 69 ms 2644 KB Output is correct
4 Correct 65 ms 2640 KB Output is correct
5 Incorrect 623 ms 10228 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 71 ms 844 KB Output is correct
2 Correct 71 ms 2896 KB Output is correct
3 Correct 71 ms 2912 KB Output is correct
4 Correct 77 ms 2700 KB Output is correct
5 Incorrect 930 ms 10752 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 3 ms 344 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 14 ms 856 KB Output is correct
6 Correct 18 ms 856 KB Output is correct
7 Correct 7 ms 600 KB Output is correct
8 Correct 11 ms 912 KB Output is correct
9 Correct 10 ms 856 KB Output is correct
10 Correct 5 ms 860 KB Output is correct
11 Correct 29 ms 860 KB Output is correct
12 Correct 31 ms 860 KB Output is correct
13 Correct 6 ms 856 KB Output is correct
14 Correct 12 ms 856 KB Output is correct
15 Correct 3 ms 600 KB Output is correct
16 Correct 4 ms 600 KB Output is correct
17 Correct 10 ms 600 KB Output is correct
18 Correct 7 ms 1112 KB Output is correct
19 Correct 10 ms 600 KB Output is correct
20 Correct 10 ms 812 KB Output is correct
21 Incorrect 1234 ms 5696 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 3 ms 344 KB Output is correct
4 Correct 4 ms 604 KB Output is correct
5 Correct 14 ms 856 KB Output is correct
6 Correct 18 ms 856 KB Output is correct
7 Correct 7 ms 600 KB Output is correct
8 Correct 11 ms 912 KB Output is correct
9 Correct 10 ms 856 KB Output is correct
10 Correct 5 ms 860 KB Output is correct
11 Correct 29 ms 860 KB Output is correct
12 Correct 31 ms 860 KB Output is correct
13 Correct 6 ms 856 KB Output is correct
14 Correct 12 ms 856 KB Output is correct
15 Correct 3 ms 600 KB Output is correct
16 Correct 4 ms 600 KB Output is correct
17 Correct 10 ms 600 KB Output is correct
18 Correct 7 ms 1112 KB Output is correct
19 Correct 10 ms 600 KB Output is correct
20 Correct 10 ms 812 KB Output is correct
21 Incorrect 1234 ms 5696 KB Output isn't correct
22 Halted 0 ms 0 KB -