Submission #285509

#TimeUsernameProblemLanguageResultExecution timeMemory
285509arnold518Arcade (NOI20_arcade)C++14
0 / 100
1 ms384 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> pii; typedef pair<ll, ll> pll; const int MAXM = 5e5; const int INF = 1e9; int N, M, T[MAXM+10], A[MAXM+10], C[MAXM+10]; pii B[MAXM+10]; int tree[MAXM+10]; void update(int i, int k) { i=M-i+1; for(; i<=M; i+=(i&-i)) tree[i]=max(tree[i], k); } int query(int i) { i=M-i+1; int ret=0; for(; i>0; i-=(i&-i)) ret=max(ret, tree[i]); return ret; } int dp[MAXM+10]; int main() { scanf("%d%d", &N, &M); for(int i=1; i<=M; i++) scanf("%d", &T[i]); for(int i=1; i<=M; i++) scanf("%d", &A[i]); for(int i=1; i<=M; i++) { int x=A[i]-T[i], y=A[i]+T[i]; B[i]={x, y}; } sort(B+1, B+M+1); vector<int> comp; for(int i=1; i<=M; i++) comp.push_back(B[i].second); sort(comp.begin(), comp.end()); comp.erase(unique(comp.begin(), comp.end()), comp.end()); for(int i=1; i<=M; i++) C[i]=lower_bound(comp.begin(), comp.end(), B[i].second)-comp.begin(); int ans=0; for(int i=1; i<=M; i++) { dp[i]=query(C[i]+1)+1; ans=max(ans, dp[i]); update(C[i], dp[i]); } printf("%d\n", ans); }

Compilation message (stderr)

Arcade.cpp: In function 'int main()':
Arcade.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   22 |  scanf("%d%d", &N, &M);
      |  ~~~~~^~~~~~~~~~~~~~~~
Arcade.cpp:23:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   23 |  for(int i=1; i<=M; i++) scanf("%d", &T[i]);
      |                          ~~~~~^~~~~~~~~~~~~
Arcade.cpp:24:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   24 |  for(int i=1; i<=M; i++) scanf("%d", &A[i]);
      |                          ~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...