Submission #1244652

#	Time	Username	Problem	Language	Result	Execution time	Memory
1244652		allin27x	Nile (IOI24_nile)	C++20	Compilation error	0 ms	0 KiB

nile

#include <bits/stdc++.h>
using namespace std;
#define int long long

struct obj {
	int a, b, w;
};

struct rg {
	int l , r, sum, mn0, mn1, ans;
};

struct link {
	int df;
	int idx; //with idx+1
};

bool comp1(obj a, obj b) {
	return a.w < b.w;
}
bool comp2(link a, link b) {
	return a.df < b.df;
}

int res = 0;
const int N = 1e5+5;
const int INF = 1e18;
rg Z[N];

set<int> lfs,rgs;
void join(int i) {
	rg R; R.l = Z[i].l; R.r = Z[i+1].r;
	R.sum = Z[i].sum + Z[i+1].sum; res -= Z[i].ans; res -= Z[i+1].ans;
	if ((Z[i].r - Z[i].l + 1)&1) swap(Z[i+1].mn0, Z[i+1].mn1);
	R.mn0 = min(Z[i].mn0, Z[i+1].mn0); R.mn1 = min(Z[i].mn1, Z[i+1].mn1);
	if ((R.r - R.l)&1) R.ans = R.sum; else R.ans = R.sum + R.mn0;
	res += R.ans;
	rgs.erase(i); lfs.erase(i+1);
	Z[R.l] = R; Z[R.r] = R;
}

void upd(int i, int nv) {
	int r = *rgs.lower_bound(i);
	rg R = Z[r]; res -= R.ans;
	R.mn0 = min(R.mn0, nv); R.mn1 = min(R.mn1, nv);
	if ((R.r - R.l)&1) R.ans = R.sum; else R.ans = R.sum + R.mn0;
	res += R.ans;
	Z[R.l] = R; Z[R.r] = R;
}

vector<long long> calculate_costs(vector<signed> W, vector<signed> A, vector<signed> B, vector<signed> E) {
	int n = W.size();
	vector<obj> p(n); for (int i=0; i<n; i++) p[i].a = A[i], p[i].b = B[i], p[i].w = W[i];
	sort(p.begin(), p.end(), comp1);
	vector<link> evs;
	for (int i=0; i<n-1; i++) {
		link t; t.df = p[i+1].w - p[i].w; t. idx = i;
		evs.push_back(t);
	}
	sort(evs.begin(), evs.end(), comp2);
	vector<pair<int,int>> qs;
	vector<int> ans((int)E.size());
	for (int i=0; i<E.size(); i++) qs.push_back({E[i], i});
	sort(qs.begin(), qs.end());
	for (int i=0; i<n; i++) {
		lfs.insert(i); rgs.insert(i);
		Z[i].l = i; Z[i].r = i; Z[i].sum = p[i].b;
		Z[i].mn0 = p[i].a-p[i].b; Z[i].ans = p[i].a; Z[i].mn1 = INF;
		res += p[i].a;
	}
	vector<link> ps2;
	for (int i=1; i<n-1; i++) {
		link t; t.df = p[i+1].w - p[i-1].w; t.idx = i;
		ps2.push_back(t);
	}
	sort(ps2.begin(), ps2.end(), comp2);
	int j=0; int t = 0;
	for (auto [d, idx]: qs) {
		while (j<evs.size() && evs[j].df <= d) {
			join(evs[j].idx); j++;
		}
		while (t<ps2.size() && ps2[t].df <= d) {
			int i = ps2[t].idx;
			upd(i, p[i].a - p[i].b);
			t++;
		}
		ans[idx] = res;

	}
	return ans;
}

Compilation message (stderr)

nile.cpp:21:16: error: expected ')' before 'a'
   21 | bool comp2(link a, link b) {
      |           ~    ^~
      |                )
nile.cpp:21:24: error: expected ')' before 'b'
   21 | bool comp2(link a, link b) {
      |           ~            ^~
      |                        )
nile.cpp:21:26: error: expression list treated as compound expression in initializer [-fpermissive]
   21 | bool comp2(link a, link b) {
      |                          ^
nile.cpp:21:28: error: expected ',' or ';' before '{' token
   21 | bool comp2(link a, link b) {
      |                            ^
nile.cpp: In function 'std::vector<long long int> calculate_costs(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
nile.cpp:55:20: error: type/value mismatch at argument 1 in template parameter list for 'template<class _Tp, class _Alloc> class std::vector'
   55 |         vector<link> evs;
      |                    ^
nile.cpp:55:20: note:   expected a type, got 'link'
nile.cpp:55:20: error: template argument 2 is invalid
nile.cpp:57:21: error: expected ';' before 't'
   57 |                 link t; t.df = p[i+1].w - p[i].w; t. idx = i;
      |                     ^~
      |                     ;
nile.cpp:57:25: error: 't' was not declared in this scope
   57 |                 link t; t.df = p[i+1].w - p[i].w; t. idx = i;
      |                         ^
nile.cpp:58:21: error: request for member 'push_back' in 'evs', which is of non-class type 'int'
   58 |                 evs.push_back(t);
      |                     ^~~~~~~~~
nile.cpp:60:18: error: request for member 'begin' in 'evs', which is of non-class type 'int'
   60 |         sort(evs.begin(), evs.end(), comp2);
      |                  ^~~~~
nile.cpp:60:31: error: request for member 'end' in 'evs', which is of non-class type 'int'
   60 |         sort(evs.begin(), evs.end(), comp2);
      |                               ^~~
nile.cpp:71:20: error: type/value mismatch at argument 1 in template parameter list for 'template<class _Tp, class _Alloc> class std::vector'
   71 |         vector<link> ps2;
      |                    ^
nile.cpp:71:20: note:   expected a type, got 'link'
nile.cpp:71:20: error: template argument 2 is invalid
nile.cpp:73:21: error: expected ';' before 't'
   73 |                 link t; t.df = p[i+1].w - p[i-1].w; t.idx = i;
      |                     ^~
      |                     ;
nile.cpp:73:25: error: 't' was not declared in this scope
   73 |                 link t; t.df = p[i+1].w - p[i-1].w; t.idx = i;
      |                         ^
nile.cpp:74:21: error: request for member 'push_back' in 'ps2', which is of non-class type 'int'
   74 |                 ps2.push_back(t);
      |                     ^~~~~~~~~
nile.cpp:76:18: error: request for member 'begin' in 'ps2', which is of non-class type 'int'
   76 |         sort(ps2.begin(), ps2.end(), comp2);
      |                  ^~~~~
nile.cpp:76:31: error: request for member 'end' in 'ps2', which is of non-class type 'int'
   76 |         sort(ps2.begin(), ps2.end(), comp2);
      |                               ^~~
nile.cpp:79:30: error: request for member 'size' in 'evs', which is of non-class type 'int'
   79 |                 while (j<evs.size() && evs[j].df <= d) {
      |                              ^~~~
nile.cpp:79:43: error: invalid types 'int[long long int]' for array subscript
   79 |                 while (j<evs.size() && evs[j].df <= d) {
      |                                           ^
nile.cpp:80:33: error: invalid types 'int[long long int]' for array subscript
   80 |                         join(evs[j].idx); j++;
      |                                 ^
nile.cpp:82:30: error: request for member 'size' in 'ps2', which is of non-class type 'int'
   82 |                 while (t<ps2.size() && ps2[t].df <= d) {
      |                              ^~~~
nile.cpp:82:43: error: invalid types 'int[long long int]' for array subscript
   82 |                 while (t<ps2.size() && ps2[t].df <= d) {
      |                                           ^
nile.cpp:83:36: error: invalid types 'int[long long int]' for array subscript
   83 |                         int i = ps2[t].idx;
      |                                    ^