Submission #200036

#	Time	Username	Problem	Language	Result	Execution time	Memory
200036		arnold518	Two Dishes (JOI19_dishes)	C++14	0 / 100	256 ms	28388 KiB

dishes

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e6;

int N, M;
ll A[MAXN+10], S[MAXN+10], P[MAXN+10];
ll B[MAXN+10], T[MAXN+10], Q[MAXN+10];
int X[MAXN+10], Y[MAXN+10];
ll slope[MAXN+10], cut;
bool chk[MAXN+10];

int main()
{
	int i, j, k;

	scanf("%d%d", &N, &M);
	for(i=1; i<=N; i++) scanf("%lld%lld%lld", &A[i], &S[i], &P[i]), A[i]+=A[i-1];
	for(i=1; i<=M; i++) scanf("%lld%lld%lld", &B[i], &T[i], &Q[i]), B[i]+=B[i-1];

	for(i=1; i<=N; i++) X[i]=upper_bound(B, B+M+1, S[i]-A[i])-B-1;
	for(i=1; i<=M; i++) Y[i]=upper_bound(A, A+N+1, T[i]-B[i])-A-1;

	vector<pii> V;
	for(i=1; i<=N; i++) V.push_back({X[i], i});
	sort(V.begin(), V.end());
	
	for(i=1; i<=N; i++) chk[i]=true;
	for(i=1; i<=N; i++) if(X[i]>=0) slope[i]=1;
	for(i=1, j=0; i<=M; i++)
	{
		for(; j<V.size() && V[j].first<i; j++) chk[V[j].second]=false;
		if(Y[i]>=0)
		{
			cut++;
			if(!chk[Y[i]+1] && slope[Y[i]+1]) slope[Y[i]+1]=0;
		}
		//for(k=1; k<=N; k++) printf("%lld ", slope[k]); printf(" : %lld\n", cut);
	}
	for(i=1; i<=N; i++) slope[i]+=slope[i-1];
	printf("%lld", slope[N]+cut);
}

Compilation message (stderr)

dishes.cpp: In function 'int main()':
dishes.cpp:36:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(; j<V.size() && V[j].first<i; j++) chk[V[j].second]=false;
         ~^~~~~~~~~
dishes.cpp:19:12: warning: unused variable 'k' [-Wunused-variable]
  int i, j, k;
            ^
dishes.cpp:21:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~
dishes.cpp:22:64: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=N; i++) scanf("%lld%lld%lld", &A[i], &S[i], &P[i]), A[i]+=A[i-1];
                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
dishes.cpp:23:64: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(i=1; i<=M; i++) scanf("%lld%lld%lld", &B[i], &T[i], &Q[i]), B[i]+=B[i-1];
                      ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 3
• Subtask 3: 0 / 7
• Subtask 4: 0 / 39
• Subtask 5: 0 / 11
• Subtask 6: 0 / 9
• Subtask 7: 0 / 17
• Subtask 8: 0 / 9