Submission #898268

#	Time	Username	Problem	Language	Result	Execution time	Memory
898268		Litusiano	Hedgehog Daniyar and Algorithms (IZhO19_sortbooks)	C++17	13 / 100	374 ms	262144 KiB

sortbooks

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include<bits/stdc++.h>
using namespace std;
#define ll int
#define endl '\n'



struct segTree{
    vector<ll> v;
    vector<ll> upd;
    int size = 1;
    void init(int n){
        while(size < n) size *= 2;
        v.assign(2 * size, 0);
        upd.assign(2 * size, 0);
    }
    void set(int l, int r, int x, int lx, int rx, ll u){
        if(lx >= l && rx <= r){
            v[x] += u * (rx - lx);
            upd[x] += u;
            return;
        }
        if(lx >= r || l >= rx) return;
        int m = (lx + rx) / 2;
        set(l, r, 2 * x + 1, lx, m, u);
        set(l, r, 2 * x + 2, m, rx, u);
        v[x] = v[2 * x + 1] + v[2 * x + 2] + upd[x] * (rx - lx);
        return;
    }
    void set(int l, int r, int u){
        return set(l, r, 0, 0, size, u);
    }
 
    void build(vector<ll> &a, int x, int lx, int rx){
        if (rx - lx == 1){
            if (lx < (int)a.size()){
                v[x] = a[lx];
            }
            return;
        }
        int m = (lx + rx) / 2;
        build(a, 2 * x + 1, lx, m);
        build(a, 2 * x + 2, m, rx);
        v[x] = v[2 * x + 1] + v[2 * x + 2];
    }
    void build(vector<ll>& a){
        build(a, 0, 0, size);
    }
 
    pair<ll, int> sum(int l, int r, int x, int lx, int rx){
        if(lx >= l && rx <= r) return {v[x], rx - lx};
        else if(lx >= r || rx <= l) return {0, 0};
        int m = (lx + rx) / 2;
        pair<ll, int> s1 = sum(l, r, 2 * x + 1, lx, m);
        pair<ll, int> s2 = sum(l, r, 2 * x + 2, m, rx);
        return {s1.first + s2.first + upd[x] * (s1.second + s2.second), (s1.second + s2.second)};
    }
 
    ll sum(int l, int r){
        pair<ll, int> p = sum(l, r, 0, 0, size);
        return p.first;
    }
};

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
  int n,q; cin>>n>>q;
  vector<int> v(n); for(int& i : v) cin>>i;
  vector<int> pre(n+1);
  vector<int> inv;
 	for(int i = 1; i<n; i++){
  	pre[i+1] = pre[i] + (v[i] < v[i-1]); 
  	if(v[i] < v[i-1]) inv.push_back(i-1);
  }
  int CNT = 0;
  vector<tuple<int,int,int,int,int>> st;
  for(int _ = 0; _<q; _++){
  	int l,r,k; cin>>l>>r>>k;
  	if(n > 100000){
  		if(pre[r] - pre[l] == 0) cout<<1<<endl;
  		else cout<<0<<endl;
  	}
  	else{
  		l--; r--;
  		int mx = 0;
  		int idx = lower_bound(inv.begin(),inv.end(),l) - inv.begin();
  		// cerr<<"INV ";
	  	for(int x = idx; x < inv.size(); x++){
	  		// cerr<<inv[x]<<" "; 
	  		if(inv[x] >= r) break;
	  		int i = inv[x];
	  		int l1 = max(0, k-i);
	  		int r1 =  v[inv[x]]-1;
	  		if(l1 > r1) continue;
	  		st.push_back({inv[x],r,l1,r1,_});
	  		// cerr<<i+1<<" "<<r<<endl;
	  		// cerr<<"QUERY: "<<i<<" "<< seg.query(i+1,r,v[i])<<endl;
	  	}
	  	CNT++;
	  	// cerr<<endl;
  	}
  }
  if(n > 100000) return 0;
  	vector<vector<pair<pair<int,int>,pair<int,int>>>> a(n); // at time i
  	for(auto x : st){
  		int l,r,l1,r1,k; tie(l,r,l1,r1,k) = x;
  		a[l].push_back({{1,k},{l1,r1}});
  		a[r].push_back({{-1,k},{l1,r1}});
  	}
  	for(int i = 0; i<n; i++){
  		a[i].push_back({{0,0},{i,i}});
  	}
  	for(auto& x : a){
  		sort(a.rbegin(), a.rend());
  	}
  	segTree seg; seg.init(1001);
  	vector<int> badpoints; unordered_multiset<int> act;
  	unordered_set<int> ans;
  	for(auto x : a){
  		for(auto y : x){
  			int tp = y.first.first;
  			int k = y.first.second;
  			int l = y.second.first;
  			int r = y.second.second;
  			if(tp == 1){
  				seg.set(l,r+1,1); act.insert(k);
  			}
  			else if(tp == 0){
  				if(seg.sum(l,l+1) == 0) continue;
  				for(int i : act) ans.insert(i);
  			}
  			else{
  				seg.set(l,r+1,-1); act.erase(act.find(k));
  			}
  		}
  	}
  	// cout<<"Q "<<q<<endl;
  	for(int i = 0; i<q; i++){
  		if(ans.count(i)) cout<<"0"<<endl;
  		else cout<<"1"<<endl;
  	}

}

Compilation message (stderr)

sortbooks.cpp: In function 'int main()':
sortbooks.cpp:91:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |     for(int x = idx; x < inv.size(); x++){
      |                      ~~^~~~~~~~~~~~
sortbooks.cpp:88:9: warning: unused variable 'mx' [-Wunused-variable]
   88 |     int mx = 0;
      |         ^~
sortbooks.cpp:116:14: warning: unused variable 'x' [-Wunused-variable]
  116 |    for(auto& x : a){
      |              ^

• Subtask 1: 0 / 8
• Subtask 2: 0 / 9
• Subtask 3: 13 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 30
• Subtask 6: 0 / 23