Submission #211248

#	Time	Username	Problem	Language	Result	Execution time	Memory
211248		socho	Mountains (NOI20_mountains)	C++14	100 / 100	626 ms	68796 KiB

Mountains

#include "bits/stdc++.h"
using namespace std;
// #define endl '\n'
#define int long long

struct node {

   int s, e, m, val;
   node *l, *r;
   node (int _s, int _e) {
       s = _s;
       e = _e;
       m = (s + e)/2;
       val = 0;
       if (s == e) return;
       l = new node(s, m);
       r = new node(m+1, e);
   }

   void upd(int p, int v) {
       if (s == p && s== e) {
           val = v;
           return;
       }
       if (p <= m) {
           l->upd(p, v);
       }
       else {
           r->upd(p, v);
       }
       val = l->val + r->val; // transition
   }

   int qry(int qs, int qe) {
       if (qs <= s && e <= qe) {
           return val;
       }
       else if (qs > e || s > qe) {
           return 0; // base case
       }
       else {
           return l->qry(qs, qe) + r->qry(qs, qe); // transition
       }
   }
} *root;

signed main() {
	
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	
	int n;
	cin >> n;
	vector<pair<int, int> > t;
	for (int i=0; i<n; i++) {
		int x;
		cin >> x;
		t.push_back(make_pair(x, i));
	}
	
	root = new node(0, n-1);
	
	sort(t.begin(), t.end());
	
	vector<vector<int> > pos;
	pos.push_back(vector<int>());
	
	for (int i=0; i<t.size(); i++) {
		if (i != 0 && t[i].first != t[i-1].first) pos.push_back(vector<int>());
		pos.back().push_back(t[i].second);
	}
	
	int ans = 0;
	
	for (int i=0; i<pos.size(); i++) {
		for (int j=0; j<pos[i].size(); j++) {
			ans += (root->qry(0, pos[i][j]-1) * root->qry(pos[i][j]+1, n-1));
		}
		for (int j=0; j<pos[i].size(); j++) {
			root->upd(pos[i][j], 1);
		}
	}
	
	cout << ans << endl;
	
	
	
}

Compilation message (stderr)

Mountains.cpp: In function 'int main()':
Mountains.cpp:67:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<t.size(); i++) {
                ~^~~~~~~~~
Mountains.cpp:74:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i=0; i<pos.size(); i++) {
                ~^~~~~~~~~~~
Mountains.cpp:75:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0; j<pos[i].size(); j++) {
                 ~^~~~~~~~~~~~~~
Mountains.cpp:78:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j=0; j<pos[i].size(); j++) {
                 ~^~~~~~~~~~~~~~

• Subtask 1: 2 / 2
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 36 / 36
• Subtask 5: 28 / 28
• Subtask 6: 9 / 9
• Subtask 7: 12 / 12