Submission #873608

#	Time	Username	Problem	Language	Result	Execution time	Memory
873608		epicci23	Segments (IZhO18_segments)	C++17	0 / 100	5078 ms	11656 KiB

segments

#include "bits/stdc++.h"
using namespace std;
//#define int long long
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define endl "\n"
#define pb push_back

/*
 dont get stuck on one approach
 write stuff on paper
 edge cases(n=1?)
 look for : dp,bs,bf,observations...
 implement and debug smarter
*/

void solve(){

  int n,t;
  cin >> n >> t;
  set<int> s;
  for(int i=1;i<n+5;i++) s.insert(i);
  
  multiset<array<int,2>> ms;
  
  array<int,2> ar[n+5];
  int last=0;

  while(n--){
  	int op;
  	cin >> op;
  	if(op==1){
  	  int a,b;
  	  cin >> a >> b;
  	  a = a ^ (t*last);
  	  b = b ^ (t*last);
  	  if(a>b) swap(a,b);
  	  int id = *s.begin();
      ar[id]={a,b};
      s.erase(id);
      ms.insert({a,b});
  	}
  	else if(op==2){
  	  int id;
  	  cin >> id;
  	  ms.erase(ms.find(ar[id]));
      s.insert(id);
  	}
  	else{
      int a,b,k;
      cin >> a >> b >> k;
      a = a ^ (t*last);
  	  b = b ^ (t*last);
  	  if(a>b) swap(a,b);
  	  int ans=0;

      for(array<int,2> x : ms){
      	int l = max(x[0],a);
      	int r = min(x[1],b);
      	if(r-l+1>=k) ans++;
      }

      last=ans;
  	  cout << ans << endl;
  	}
  }
}

int32_t main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int t=1;//cin >> t;
  while(t--) solve();
}

• Subtask 1: 0 / 7
• Subtask 2: 0 / 15
• Subtask 3: 0 / 16
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20
• Subtask 6: 0 / 25