Submission #1295993

#TimeUsernameProblemLanguageResultExecution timeMemory
1295993nathako9nLightning Rod (NOI18_lightningrod)C++20
7 / 100
1100 ms156168 KiB
#include <bits/stdc++.h> using namespace std; #define int long long #define ll long long const int N = 1e7+2; pair<int,int> ar[N+2]; int n; vector<int>pos; signed main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for(int i =1;i<=n;i++){ int x, y; cin >> x >> y; ar[i]= {x+y, x-y}; } sort(ar+1, ar+n+1, greater<pair<int,int>>()); vector<int> tail; for(int i=0;i<n;i++){ int val = ar[i+1].second; auto it = lower_bound(tail.begin(), tail.end(), -val); if(it==tail.end()) tail.push_back(-val); else *it = -val; } cout<<tail.size()<<"\n"; return 0; }
#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...