Submission #1184935

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184935		NotLinux	Inspections (NOI23_inspections)	C++20	100 / 100	681 ms	46040 KiB

Main

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)x.size()
#define all(x) x.begin() , x.end()
void solve(){
    int n,m,q;
    cin >> n >> m >> q;
    int l[m] , r[m];
    for(int i = 0;i<m;i++)
    	cin >> l[i] >> r[i];
    set<array<long long,3>>ste;// rangeleri tut
    multiset<pair<long long,long long>>ans;// pos val
    long long curtime = 0;
    for(int i = 0;i<m;i++){
    	// cout << "i : " << i << " , " << l[i] << " " << r[i] << " " << curtime << endl;
    	auto it = ste.lower_bound({l[i]+1,0,0});
    	if(it != ste.begin() and !ste.empty()){// it - 1 i isle
    		auto tmp = *prev(it);
    		// cout << "tmp : " << tmp[0] << " " << tmp[1] << " " << tmp[2] << endl;
    		if(l[i] > tmp[1] or r[i] < tmp[0]){// ortak nokta yoksa
    			37;
    		}
    		else if(l[i] <= tmp[0] and r[i] >= tmp[1]){// ben tmp yi kapliosam
    			ans.insert({(curtime + tmp[0] - l[i]) - tmp[2] , tmp[1] - tmp[0] + 1});
    			// cout << "ans : " << (curtime + tmp[0] - l[i]) - tmp[2] << " , " << tmp[1] - tmp[0] + 1 << endl;
    			ste.extract(prev(it));
    		}
    		else if(l[i] >= tmp[0] and r[i] <= tmp[1]){// o beni kapliosa
    			ans.insert({curtime - (tmp[2] + l[i] - tmp[0]) , r[i] - l[i] + 1});
    			// cout << "ans : " << curtime - (tmp[2] + l[i] - tmp[0]) << " , " << r[i] - l[i] + 1 << endl;
    			ste.extract(prev(it));
    			ste.insert({tmp[0],l[i]-1,tmp[2]});
    			ste.insert({r[i]+1,tmp[1],tmp[2] + r[i]+1 - tmp[0]});
    		}
    		else {// kesisiosak
    			if(tmp[0] < l[i]){// o soldaysa
    				ans.insert({curtime - (tmp[2] + l[i] - tmp[0]) , tmp[1] - l[i] + 1});
    				// cout << "ans : " << curtime - (tmp[2] + l[i] - tmp[0]) << " , " << tmp[1] - l[i] + 1 << endl;
    				ste.extract(prev(it));
    				ste.insert({tmp[0],l[i]-1,tmp[2]});
    			}
    			else{// ben soldaysam
    				ans.insert({(curtime + tmp[0] - l[i]) - tmp[2] , r[i] - tmp[0] + 1});
    				// cout << "ans : " << (curtime + tmp[0] - l[i]) - tmp[2] << " , " << r[i] - tmp[0] + 1 << endl;
    				ste.extract(prev(it));
    				ste.insert({r[i]+1,tmp[1],tmp[2] + r[i]+1 - tmp[0]});
    			}
    		}
    	}
    	while(it != ste.end()){
    		auto tmp = *it;
    		it = next(it);
    		// cout << "tmp : " << tmp[0] << " " << tmp[1] << " " << tmp[2] << endl;
    		if(l[i] > tmp[1] or r[i] < tmp[0]){// ortak nokta yoksa
    			if(r[i] < tmp[0])break;
    		}
    		else if(l[i] <= tmp[0] and r[i] >= tmp[1]){// ben tmp yi kapliosam
    			ans.insert({(curtime + tmp[0] - l[i]) - tmp[2] , tmp[1] - tmp[0] + 1});
    			// cout << "ans : " << (curtime + tmp[0] - l[i]) - tmp[2] << " , " << tmp[1] - tmp[0] + 1 << endl;
    			ste.extract(prev(it));
    		}
    		else if(l[i] >= tmp[0] and r[i] <= tmp[1]){// o beni kapliosa
    			ans.insert({curtime - (tmp[2] + l[i] - tmp[0]) , r[i] - l[i] + 1});
    			// cout << "ans : " << curtime - (tmp[2] + l[i] - tmp[0]) << " , " << r[i] - l[i] + 1 << endl;
    			ste.extract(prev(it));
    			ste.insert({tmp[0],l[i]-1,tmp[2]});
    			ste.insert({r[i]+1,tmp[1],tmp[2] + r[i]+1 - tmp[0]});
    		}
    		else {// kesisiosak
    			if(tmp[0] < l[i]){// o soldaysa
    				ans.insert({curtime - (tmp[2] + l[i] - tmp[0]) , tmp[1] - l[i] + 1});
    				// cout << "ans : " << curtime - (tmp[2] + l[i] - tmp[0]) << " , " << tmp[1] - l[i] + 1 << endl;
    				ste.extract(prev(it));
    				ste.insert({tmp[0],l[i]-1,tmp[2]});
    			}
    			else{// ben soldaysam
    				ans.insert({(curtime + tmp[0] - l[i]) - tmp[2] , r[i] - tmp[0] + 1});
    				// cout << "ans : " << (curtime + tmp[0] - l[i]) - tmp[2] << " , " << r[i] - tmp[0] + 1 << endl;
    				ste.extract(prev(it));
    				ste.insert({r[i]+1,tmp[1],tmp[2] + r[i]+1 - tmp[0]});
    			}
    		}
    	}
    	ste.insert({l[i],r[i],curtime});
    	curtime += r[i] - l[i] + 1;
    }
    pair<long long,int>s[q];
    for(int i = 0;i<q;i++){
    	cin >> s[i].first;
    	s[i].second = i;
    }
    sort(s , s + q);
    long long cevap[q] , sum = 0;
    for(auto itr : ans)sum += itr.second;
    memset(cevap,-1,sizeof(cevap));
    auto it = ans.begin();
    for(int i = 0;i<q;i++){
    	while(it != ans.end() and (*it).first <= s[i].first){
    		sum -= (*it).second;
    		it = next(it);
    	}
    	cevap[s[i].second] = sum;
    }
    for(int i = 0;i<q;i++)
    	cout << cevap[i] << " ";
    cout << endl;
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	int testcase=1;//cin >> testcase;
	while(testcase--)solve();
	cerr << 1000.0 * clock() / CLOCKS_PER_SEC << " ms" << endl;
}

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