oj.uz

Submission #919012

# Submission time Handle Problem Language Result Execution time Memory
919012 2024-01-31T04:17:00 Z imarn Segments (IZhO18_segments) C++14
7 / 100
 1225 ms 13568 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>
#define int ll
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]=2e12+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];
int32_t 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:24:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i=0;i<cur.size();i++){
      |                 ~^~~~~~~~~~~
segments.cpp: In function 'int32_t main()':
segments.cpp:82:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   82 |             if(a>b)swap(a,b);seg[id]={a,b};
      |             ^~
segments.cpp:82:30: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   82 |             if(a>b)swap(a,b);seg[id]={a,b};
      |                              ^~~

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 3 ms 344 KB Output is correct
5 Correct 13 ms 1012 KB Output is correct
6 Correct 17 ms 856 KB Output is correct
7 Correct 7 ms 600 KB Output is correct
8 Correct 11 ms 856 KB Output is correct
9 Correct 9 ms 856 KB Output is correct
10 Correct 5 ms 860 KB Output is correct
11 Correct 29 ms 904 KB Output is correct
12 Correct 30 ms 856 KB Output is correct
13 Correct 6 ms 856 KB Output is correct
14 Correct 17 ms 908 KB Output is correct
15 Correct 3 ms 344 KB Output is correct
16 Correct 4 ms 344 KB Output is correct
17 Correct 11 ms 600 KB Output is correct
18 Correct 7 ms 860 KB Output is correct
19 Correct 9 ms 604 KB Output is correct
20 Correct 13 ms 856 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1225 ms 9088 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 2644 KB Output is correct
2 Correct 65 ms 2820 KB Output is correct
3 Correct 68 ms 2928 KB Output is correct
4 Correct 64 ms 2640 KB Output is correct
5 Incorrect 662 ms 13568 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 2648 KB Output is correct
2 Correct 71 ms 2648 KB Output is correct
3 Correct 71 ms 2808 KB Output is correct
4 Correct 78 ms 2648 KB Output is correct
5 Incorrect 965 ms 13512 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 3 ms 344 KB Output is correct
5 Correct 13 ms 1012 KB Output is correct
6 Correct 17 ms 856 KB Output is correct
7 Correct 7 ms 600 KB Output is correct
8 Correct 11 ms 856 KB Output is correct
9 Correct 9 ms 856 KB Output is correct
10 Correct 5 ms 860 KB Output is correct
11 Correct 29 ms 904 KB Output is correct
12 Correct 30 ms 856 KB Output is correct
13 Correct 6 ms 856 KB Output is correct
14 Correct 17 ms 908 KB Output is correct
15 Correct 3 ms 344 KB Output is correct
16 Correct 4 ms 344 KB Output is correct
17 Correct 11 ms 600 KB Output is correct
18 Correct 7 ms 860 KB Output is correct
19 Correct 9 ms 604 KB Output is correct
20 Correct 13 ms 856 KB Output is correct
21 Incorrect 1225 ms 9088 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 4 ms 348 KB Output is correct
4 Correct 3 ms 344 KB Output is correct
5 Correct 13 ms 1012 KB Output is correct
6 Correct 17 ms 856 KB Output is correct
7 Correct 7 ms 600 KB Output is correct
8 Correct 11 ms 856 KB Output is correct
9 Correct 9 ms 856 KB Output is correct
10 Correct 5 ms 860 KB Output is correct
11 Correct 29 ms 904 KB Output is correct
12 Correct 30 ms 856 KB Output is correct
13 Correct 6 ms 856 KB Output is correct
14 Correct 17 ms 908 KB Output is correct
15 Correct 3 ms 344 KB Output is correct
16 Correct 4 ms 344 KB Output is correct
17 Correct 11 ms 600 KB Output is correct
18 Correct 7 ms 860 KB Output is correct
19 Correct 9 ms 604 KB Output is correct
20 Correct 13 ms 856 KB Output is correct
21 Incorrect 1225 ms 9088 KB Output isn't correct
22 Halted 0 ms 0 KB -