Submission #952402

#TimeUsernameProblemLanguageResultExecution timeMemory
952402MinbaevMagic Tree (CEOI19_magictree)C++17
11 / 100
330 ms5320 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; #define pb push_back #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define f first #define int long long #define s second #define pii pair<int,int> template<class T>bool umax(T &a,T b){if(a<b){a=b;return true;}return false;} template<class T>bool umin(T &a,T b){if(b<a){a=b;return true;}return false;} typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; const int N = 1e6 + 5; const int inf = 1e17 + 7; const int mod = 1e9 + 7; int n,m,k; vector<int>ans,a; void solve(){ cin >> n >> m >> k; for(int i = 2;i<=n;i++){ int b; cin >> b; } vector<int>g(n+1); for(int i = 0;i<m;i++){ int b,c,d; cin >> b >> c >> d; g[b] = c; } for(int i = 1;i<=n;i++){ if(g[i] == 0)continue; a.pb(-g[i]); } for(int i = 0;i<a.size();i++){ if(ans.size() > 0 && a[i] >= ans[ans.size()-1]){ ans.pb(a[i]); } else{ auto it = lower_bound(all(ans),a[i]); if(it != ans.end()){ while(*it == a[i])it++; *it = a[i]; } else ans.pb(a[i]); } //~ for(auto to:ans)cout<<to<<" "; //~ cout<<"\n"; } //~ for(auto to:a)cout<<to<<" "; //~ cout<<"\n"; cout << ans.size()<<"\n"; } /* 6 6 2 1 2 3 4 5 1 1 1 2 2 2 3 3 1 4 4 2 5 5 2 6 6 1 // Success consists of going from failure to failure without loss of enthusiasm // Problems means that you are trying // Soberis dolboyeb */ signed main() { // freopen("seq.in", "r", stdin); // freopen("seq.out", "w", stdout); ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL); int tt=1;//cin>>tt; while(tt--)solve(); }

Compilation message (stderr)

magictree.cpp: In function 'void solve()':
magictree.cpp:48:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for(int i = 0;i<a.size();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...
#Verdict Execution timeMemoryGrader output
Fetching results...