Submission #1234833

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234833		PenguinsAreCute	Long Distance Coach (JOI17_coach)	C++17	Compilation error	0 ms	0 KiB

coach

struct seg {
	int n;
	vector<long long> val;
	seg(int _n): n(_n), val(2*_n,1e18) {}
	void up(int x, long long u) {
		for(x+=n;x;x>>=1)
			val[x] = min(val[x], u);
	}
	long long qry(int l, int r) {
		long long ans = 1e18;
		for(l+=n,r+=n;l<r;l>>=1,r>>=1) {
			if(l&1)
				ans=min(ans,val[l++]);
			if(r&1)
				ans=min(ans,val[--r]);
		}
		return ans;
	}
};

int main() {
	long long x, t, w;
	int n, m;
	cin >> x >> n >> m >> w >> t;
	seg tree(n+1);
	long long s[n+1];
	for(int i=0;i<n;i++)
		cin >> s[i];
	s[n++] = x;
	long long u[n];
	memcpy(u,s,sizeof(u));
	for(int i=0;i<n;i++)
		u[i] %= t;
	sort(u,u+n);
	for(int i=0;i<n;i++) {
		int id = lower_bound(u,u+n+1,s[i]%t)-u;
		tree.up(id,s[i]);
	}

	pair<long long, long long> ppl[m+1];
	for(int i=0;i<m;i++)
		cin >> ppl[i].first >> ppl[i].second;
	ppl[m++] = {0, 1e18};
	long long d[m], c[m];
	sort(s,s+n);
	sort(ppl,ppl+m);
	for(int i=0;i<m;i++)
		d[i] = ppl[i].first, c[i] = ppl[i].second;

	pair<long long,int> dp[m+1];
	fill(dp,dp+m+1,make_pair((long long)1e18,0));
	dp[m] = {0,m};
	for(int i=m;i;i--) {
		long long cur = 0;
		for(int j=i;j--;) {
			dp[j] = min(dp[j], {dp[i].first + cur, i});
			long long minT = tree.qry(lower_bound(u,u+n,d[j])-u,i==m?n:lower_bound(u,u+n,d[i])-u);
			minT -= (minT % t);
			minT += d[j];
			if(minT < 1e17)
				cur += c[j] - (x - minT) / t * w - w;
			else
				cur = 1e18;
		}
	}
	for(int i=0;i<m;i++)
		assert(dp[i].second == i+1 || dp[i].second >= dp[i+1].second);

	long long ans = dp[0].first;
	for(int i=0;i<m;i++)
		ans += w * ((x - d[i]) / t + 1);
	cout << ans;
}

Compilation message (stderr)

coach.cpp:4:9: error: 'vector' does not name a type
    4 |         vector<long long> val;
      |         ^~~~~~
coach.cpp: In constructor 'seg::seg(int)':
coach.cpp:5:29: error: class 'seg' does not have any field named 'val'
    5 |         seg(int _n): n(_n), val(2*_n,1e18) {}
      |                             ^~~
coach.cpp: In member function 'void seg::up(int, long long int)':
coach.cpp:8:25: error: 'val' was not declared in this scope
    8 |                         val[x] = min(val[x], u);
      |                         ^~~
coach.cpp:8:34: error: 'min' was not declared in this scope
    8 |                         val[x] = min(val[x], u);
      |                                  ^~~
coach.cpp: In member function 'long long int seg::qry(int, int)':
coach.cpp:14:45: error: 'val' was not declared in this scope
   14 |                                 ans=min(ans,val[l++]);
      |                                             ^~~
coach.cpp:14:37: error: 'min' was not declared in this scope
   14 |                                 ans=min(ans,val[l++]);
      |                                     ^~~
coach.cpp:16:45: error: 'val' was not declared in this scope
   16 |                                 ans=min(ans,val[--r]);
      |                                             ^~~
coach.cpp:16:37: error: 'min' was not declared in this scope
   16 |                                 ans=min(ans,val[--r]);
      |                                     ^~~
coach.cpp: In function 'int main()':
coach.cpp:25:9: error: 'cin' was not declared in this scope
   25 |         cin >> x >> n >> m >> w >> t;
      |         ^~~
coach.cpp:32:9: error: 'memcpy' was not declared in this scope
   32 |         memcpy(u,s,sizeof(u));
      |         ^~~~~~
coach.cpp:1:1: note: 'memcpy' is defined in header '<cstring>'; did you forget to '#include <cstring>'?
  +++ |+#include <cstring>
    1 | 
coach.cpp:35:9: error: 'sort' was not declared in this scope; did you mean 'short'?
   35 |         sort(u,u+n);
      |         ^~~~
      |         short
coach.cpp:37:26: error: 'lower_bound' was not declared in this scope
   37 |                 int id = lower_bound(u,u+n+1,s[i]%t)-u;
      |                          ^~~~~~~~~~~
coach.cpp:41:9: error: 'pair' was not declared in this scope
   41 |         pair<long long, long long> ppl[m+1];
      |         ^~~~
coach.cpp:41:14: error: expected primary-expression before 'long'
   41 |         pair<long long, long long> ppl[m+1];
      |              ^~~~
coach.cpp:43:24: error: 'ppl' was not declared in this scope
   43 |                 cin >> ppl[i].first >> ppl[i].second;
      |                        ^~~
coach.cpp:44:9: error: 'ppl' was not declared in this scope
   44 |         ppl[m++] = {0, 1e18};
      |         ^~~
coach.cpp:51:14: error: expected primary-expression before 'long'
   51 |         pair<long long,int> dp[m+1];
      |              ^~~~
coach.cpp:52:14: error: 'dp' was not declared in this scope; did you mean 'd'?
   52 |         fill(dp,dp+m+1,make_pair((long long)1e18,0));
      |              ^~
      |              d
coach.cpp:52:24: error: 'make_pair' was not declared in this scope
   52 |         fill(dp,dp+m+1,make_pair((long long)1e18,0));
      |                        ^~~~~~~~~
coach.cpp:52:9: error: 'fill' was not declared in this scope
   52 |         fill(dp,dp+m+1,make_pair((long long)1e18,0));
      |         ^~~~
coach.cpp:57:33: error: 'min' was not declared in this scope; did you mean 'main'?
   57 |                         dp[j] = min(dp[j], {dp[i].first + cur, i});
      |                                 ^~~
      |                                 main
coach.cpp:58:51: error: 'lower_bound' was not declared in this scope
   58 |                         long long minT = tree.qry(lower_bound(u,u+n,d[j])-u,i==m?n:lower_bound(u,u+n,d[i])-u);
      |                                                   ^~~~~~~~~~~
coach.cpp:68:17: error: 'assert' was not declared in this scope
   68 |                 assert(dp[i].second == i+1 || dp[i].second >= dp[i+1].second);
      |                 ^~~~~~
coach.cpp:1:1: note: 'assert' is defined in header '<cassert>'; did you forget to '#include <cassert>'?
  +++ |+#include <cassert>
    1 | 
coach.cpp:73:9: error: 'cout' was not declared in this scope
   73 |         cout << ans;
      |         ^~~~