Submission #378368

#	Time	Username	Problem	Language	Result	Execution time	Memory
378368		Mounir	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	205 ms	14172 KiB

fancyfence

#include <bits/stdc++.h>
#define int long long
#define chmin(x, v) x = min(x, v)
#define chmax(x, v) x = max(x, v)
#define all(v) v.begin(), v.end()
using namespace std;
 
const int MOD = 1e9 + 7, N = 2e5;
set<int> pasVisites;
 
int nInters(int len){
	return ((len * (len + 1))/2)%MOD;
}
 
int subSum(int n){
	return ((n * (n+1))/2)%MOD;
}
 
struct Zone {
	int hauteur, largeur, ind;
	
	bool operator < (const Zone &autre) const {
		if (hauteur != autre.hauteur) return hauteur > autre.hauteur;
		return largeur < autre.largeur;
	}
};
 
 
signed main(){
	int nZones; cin >> nZones;
	vector<int> hauteurs(nZones), largeurs(nZones);
	for (int& hauteur : hauteurs) cin >> hauteur;
	for (int& largeur : largeurs) cin >> largeur;
	
	vector<Zone> zones, pastriees;
	for (int i = 0; i < nZones; ++i){
		if (zones.size() == 0 || zones[zones.size() - 1].hauteur != hauteurs[i])
			zones.push_back({hauteurs[i], 0, (int)zones.size()});
		zones[zones.size() - 1].largeur = (zones[zones.size() - 1].largeur + largeurs[i])%MOD;
	}
	
	
	vector<int> cumul(zones.size());
	for (int i = 0; i < (int)zones.size(); ++i){
		cumul[i] = zones[i].largeur;
		if (i != 0)
			cumul[i] = (cumul[i] + cumul[i - 1])%MOD;
		pasVisites.insert(i);
	}
	
	pastriees = zones;
	sort(all(zones));
	int sum = 0;
	for (Zone& zone : zones){
		pasVisites.erase(zone.ind);
		auto it = pasVisites.upper_bound(zone.ind);
		int gauche = -1, droite = zones.size() - 1;
		if (it != pasVisites.end()) droite = *it - 1;
		if (it != pasVisites.begin()){
			it--;
			gauche = *it;
		}
		int len = cumul[droite];
		if (gauche != -1) len -= cumul[gauche];
		len = (len + MOD)%MOD;
		
		/* Trouver la hauteur */
		int maxi = 0;
		if (gauche != -1) chmax(maxi, pastriees[gauche].hauteur);
		if (droite + 1 < (int)zones.size())chmax(maxi, pastriees[droite + 1].hauteur);
		int s = subSum(zone.hauteur) - subSum(maxi);
		
		sum = (sum + nInters(len) * (s))%MOD;
	}
	cout << sum << endl;
	return 0;
}

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 27 / 27