Submission #914226

#	Time	Username	Problem	Language	Result	Execution time	Memory
914226		Litusiano	Inspections (NOI23_inspections)	C++17	77 / 100	2015 ms	30108 KiB

Main

#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math,inline")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,lzcnt,mmx,abm,avx,avx2,fma")
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll int
const int inf = 1e18;

struct SegTree{
  int n;
  vector<int> seg;
  vector<int> lazy;
  void build(int n1){
    n = 1;
    while(n < n1) n*=2;
    seg.resize(2*n); lazy.resize(2*n,0);
    for(int i = 0; i<2*n; i++){
      lazy[i] = seg[i] = 0;
    }
  }
 
  void pushDown(int k){
    seg[2*k] = lazy[k];
    lazy[2*k] = lazy[k];
    seg[2*k+1] = lazy[k];
    lazy[2*k+1] = lazy[k];
    lazy[k] = 0;
  }
 
  int query(int ql, int qr, int k, int l, int r){
        if(ql <= l && r <= qr){
            return seg[k];
        }
        if(l > qr || r < ql) return -10;
        int m = (l+r)/2;
        if(lazy[k]) pushDown(k);
        int x = query(ql,qr,2*k, l, m);
        int y = query(ql,qr,2*k+1, m+1, r);
        if(min(x,y) > -10 && x != y) return -1;
        return max(x,y);
    }
    int query(int ql, int qr){
        return query(ql,qr,1,0,n-1);
    }
    void update(int ql, int qr, int v, int k, int l, int r){
        if(ql <= l && r <= qr){
            lazy[k] = v;
            seg[k] = v;
            return;
        }
        if(l > qr || r < ql) return;
        int m = (l+r)/2;
        if(lazy[k]) pushDown(k);
        update(ql,qr,v,2*k, l, m);
        update(ql,qr,v,2*k+1, m+1, r);
        if(seg[2*k] == seg[2*k+1]) seg[k] = seg[2*k];
        else seg[k] = -1;
    }
    void update(int ql, int qr, int v){
        update(ql,qr,v,1,0,n-1);
    }
};



signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n,m,q; cin>>n>>m>>q;
	SegTree seg; seg.build(n+1);
	vector<pair<int,int>> sgs;
	vector<pair<int,int>> Ori;
	vector<int> pre(m+1);
	for(int i = 1; i<=m; i++){
		int l,r; cin>>l>>r;
		pre[i] = pre[i-1] + r-l+1;
		// what is last value of act
		int act = l;
		Ori.push_back({l,r});
		while(act <= r){
			int z = seg.query(act,act);
			int l1 = act; int r1 = r+1;
			while(r1 > l1+1){
				int m1 = (l1+r1)/2;
				if(seg.query(act,m1) == z) l1 = m1;
				else r1 = m1;
			}
			// cerr<<endl<<"I: "<<i<<" "<<z;
			int dist = act-l + max(0ll,pre[i-1] - pre[z]);
			if(z != 0) 	dist += Ori[z-1].second - act +1;
			// if(z) cerr<<" ACT: "<<act<<" "<<l1<<" DIST: "<<dist<<" "<<z<<endl;
			if(z != 0) sgs.push_back({dist,l1-act+1,});
			act = l1+1;
		}
		seg.update(l,r,i);
		// cerr<<"QUERY "<<seg.query(l,r)<<endl;
		// THERE ARE SEGMENTS WITH A VALUE DIST, of certain sz
	}
	sort(sgs.begin(),sgs.end());
	vector<int> pre1(sgs.size()+1);
	for(int i = 0; i<sgs.size(); i++){
		pre1[i+1] = pre1[i] + sgs[i].second;
	}
	while(q--){
		int a; cin>>a;
		pair<int,int> p = {a,inf};
		int id = lower_bound(sgs.begin(),sgs.end(), p) - sgs.begin();
		cout<<pre1[sgs.size()]-pre1[id]<<" ";
	}
}	

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:101:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |  for(int i = 0; i<sgs.size(); i++){
      |                 ~^~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 26 / 26
• Subtask 5: 0 / 23