oj.uz

Submission #873603

# Submission time Handle Problem Language Result Execution time Memory
873603 2023-11-15T11:23:01 Z epicci23 Segments (IZhO18_segments) C++17
0 / 100
 5000 ms 22772 KB 
#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<=2*n;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);
  	  ar[id]={-1,-1};
  	}
  	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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 2 ms 1880 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5073 ms 13804 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 39 ms 22640 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 39 ms 22772 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 2 ms 1880 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Runtime error 2 ms 1880 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -