oj.uz

Submission #898507

# Submission time Handle Problem Language Result Execution time Memory
898507 2024-01-04T19:22:34 Z Denkata Segments (IZhO18_segments) C++14
15 / 100
 860 ms 7304 KB 
///mnogo trqbva da se vnimava s lower/upperbound queryta v pair
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+3;
const int crit = 2000;
int i,j,p,q,n,m,k,L,R,A,B,lans,id,lb[maxn],rb[maxn],block[maxn],minlen[maxn],t,curlen;
vector < pair <int,int> > cur,all;
vector < pair <int,int> > levi[100],desni[100];//n/crit
int removed[maxn];
void insert(int l,int r,int nom)
{
    cur.push_back({r-l+1,nom});
    if(cur.size()==crit)
    {
        vector <pair <int,int>> neww;

        for(i=0; i<=all.size()/crit+2; i++)
            levi[i].clear(),desni[i].clear(),minlen[i] = -1;
        for(auto i:cur)
            neww.push_back(i);
        for(auto i:all)
            neww.push_back(i);
        cur.clear();
        all.clear();
        for(auto i:neww)
        {
            if(!removed[i.second])
                all.push_back(i);
        }

        ///build the structure
        sort(all.rbegin(),all.rend());
        int bl = 0;
        int br = 0;
        int Min = INT_MAX;
        for(auto i:all)
        {
            levi[bl].push_back({lb[i.second],i.second});
            desni[bl].push_back({rb[i.second],i.second});
            Min = min(Min,i.first);
            block[i.second] = bl;
            br++;
            if(br==crit)
            {
                minlen[bl] = Min;
                Min = INT_MAX;
                bl++;
                br = 0;
            }
        }

        for(i=0; i<=all.size()/crit+2; i++)
        {
            if(levi[i].empty())break;
            sort(levi[i].begin(),levi[i].end());
            sort(desni[i].begin(),desni[i].end());
        }
    }
}
void remove(int id)
{
    removed[id] = true;
    if(block[id]==-1)
    {
        vector < pair <int,int> > newws;
        for(auto i:cur)
            if(i.second!=id)newws.push_back(i);
        cur = newws;
        return ;
    }
    p = block[id];

    vector < pair <int,int> > newws;
    for(auto i:levi[p])
        if(i.second!=id)newws.push_back(i);
    levi[p] = newws;

    newws.clear();
    for(auto i:desni[p])
        if(i.second!=id)newws.push_back(i);
    desni[p] = newws;

    block[id] = -1;
}
int solve(int l,int r,int k)
{
    int ans = 0;
    for(auto i:cur)
    {
        //cout<<lb[i.second]<<" "<<rb[i.second]<<"    "<<l<<" "<<r<<" "<<k<<endl;
        if(min(rb[i.second],r)-max(lb[i.second],l)+1>=k)
            ans++;
    }
    for(i=0; i<=all.size()/crit+1; i++)
    {
        if(minlen[i]==-1)break;
        if(minlen[i]<k)
        {
            ///iterative check
            j = i;
            for(auto i:levi[j])
            {
                if(removed[i.second])
                    continue;
                if(min(rb[i.second],r)-max(lb[i.second],l)+1>=k)
                    ans++;
            }
            break;
        }
        ans+=levi[i].size();
        p = 0;
        ///indexed from 0
        p += upper_bound(desni[i].begin(),desni[i].end(), make_pair(l+k-2,10000000))-desni[i].begin();
        p += levi[i].size()-(lower_bound(levi[i].begin(),levi[i].end(), make_pair(r-k+2,-1))-levi[i].begin());
        ans-=p;
    }
    return ans;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>n>>t;
    for(i=0; i<=n; i++)
        block[i] = -1,minlen[i] = -1;
    lans = 0;
    while(n--)
    {
        int type;
        cin>>type;
        if(type==1)
        {
            cin>>A>>B;
            L = A^(t*lans);
            R = B^(t*lans);
            if(L>R)swap(L,R);
            curlen++;
            lb[curlen] = L;
            rb[curlen] = R;
            insert(L,R,curlen);
        }
        else if(type==2)
        {
            cin>>id;
            remove(id);
        }
        else
        {
            cin>>A>>B>>k;
            L = A^(t*lans);
            R = B^(t*lans);
            if(L>R)swap(L,R);
            lans = solve(L,R,k);
            cout<<lans<<endl;
        }
    }
    return 0;
}
/**
6 1
1 1 2
3 2 4 2
1 3 5
3 2 3 1
2 1
3 0 3 1



6 0
1 3 10
1 3 5
3 6 10 6
2 1
1 3 10
3 6 4 2
*/

Compilation message

segments.cpp: In function 'void insert(int, int, int)':
segments.cpp:17:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         for(i=0; i<=all.size()/crit+2; i++)
      |                  ~^~~~~~~~~~~~~~~~~~~
segments.cpp:52:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |         for(i=0; i<=all.size()/crit+2; i++)
      |                  ~^~~~~~~~~~~~~~~~~~~
segments.cpp: In function 'int solve(int, int, int)':
segments.cpp:94:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |     for(i=0; i<=all.size()/crit+1; i++)
      |              ~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 4 ms 2548 KB Output is correct
4 Correct 4 ms 2524 KB Output is correct
5 Correct 7 ms 2652 KB Output is correct
6 Correct 12 ms 2652 KB Output is correct
7 Correct 8 ms 2396 KB Output is correct
8 Correct 10 ms 2652 KB Output is correct
9 Correct 11 ms 2652 KB Output is correct
10 Correct 5 ms 2652 KB Output is correct
11 Correct 17 ms 2660 KB Output is correct
12 Correct 17 ms 2904 KB Output is correct
13 Correct 5 ms 2652 KB Output is correct
14 Correct 11 ms 2652 KB Output is correct
15 Correct 3 ms 2396 KB Output is correct
16 Correct 4 ms 2396 KB Output is correct
17 Correct 10 ms 2396 KB Output is correct
18 Incorrect 7 ms 2652 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 813 ms 4904 KB Output is correct
2 Correct 793 ms 4684 KB Output is correct
3 Correct 772 ms 4772 KB Output is correct
4 Correct 696 ms 5148 KB Output is correct
5 Correct 445 ms 7084 KB Output is correct
6 Correct 453 ms 7188 KB Output is correct
7 Correct 789 ms 4772 KB Output is correct
8 Correct 761 ms 4828 KB Output is correct
9 Correct 765 ms 4696 KB Output is correct
10 Correct 780 ms 3780 KB Output is correct
11 Correct 748 ms 3892 KB Output is correct
12 Correct 585 ms 6200 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 2900 KB Output is correct
2 Correct 69 ms 2852 KB Output is correct
3 Correct 125 ms 3032 KB Output is correct
4 Correct 71 ms 2896 KB Output is correct
5 Correct 438 ms 6224 KB Output is correct
6 Correct 385 ms 5320 KB Output is correct
7 Correct 443 ms 5528 KB Output is correct
8 Correct 432 ms 7080 KB Output is correct
9 Incorrect 423 ms 7304 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 2848 KB Output is correct
2 Correct 75 ms 2904 KB Output is correct
3 Correct 71 ms 2912 KB Output is correct
4 Correct 79 ms 2896 KB Output is correct
5 Correct 570 ms 6596 KB Output is correct
6 Correct 860 ms 3828 KB Output is correct
7 Correct 559 ms 6552 KB Output is correct
8 Correct 673 ms 3500 KB Output is correct
9 Incorrect 499 ms 4804 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 4 ms 2548 KB Output is correct
4 Correct 4 ms 2524 KB Output is correct
5 Correct 7 ms 2652 KB Output is correct
6 Correct 12 ms 2652 KB Output is correct
7 Correct 8 ms 2396 KB Output is correct
8 Correct 10 ms 2652 KB Output is correct
9 Correct 11 ms 2652 KB Output is correct
10 Correct 5 ms 2652 KB Output is correct
11 Correct 17 ms 2660 KB Output is correct
12 Correct 17 ms 2904 KB Output is correct
13 Correct 5 ms 2652 KB Output is correct
14 Correct 11 ms 2652 KB Output is correct
15 Correct 3 ms 2396 KB Output is correct
16 Correct 4 ms 2396 KB Output is correct
17 Correct 10 ms 2396 KB Output is correct
18 Incorrect 7 ms 2652 KB Output isn't correct
19 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 4 ms 2548 KB Output is correct
4 Correct 4 ms 2524 KB Output is correct
5 Correct 7 ms 2652 KB Output is correct
6 Correct 12 ms 2652 KB Output is correct
7 Correct 8 ms 2396 KB Output is correct
8 Correct 10 ms 2652 KB Output is correct
9 Correct 11 ms 2652 KB Output is correct
10 Correct 5 ms 2652 KB Output is correct
11 Correct 17 ms 2660 KB Output is correct
12 Correct 17 ms 2904 KB Output is correct
13 Correct 5 ms 2652 KB Output is correct
14 Correct 11 ms 2652 KB Output is correct
15 Correct 3 ms 2396 KB Output is correct
16 Correct 4 ms 2396 KB Output is correct
17 Correct 10 ms 2396 KB Output is correct
18 Incorrect 7 ms 2652 KB Output isn't correct
19 Halted 0 ms 0 KB -