Submission #835501

#TimeUsernameProblemLanguageResultExecution timeMemory
835501vjudge1Exam (eJOI20_exam)C++14
100 / 100
106 ms10940 KiB
#include<bits/stdc++.h> #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") using namespace std; #define ll long long #define rep(i,n,N) for(int i = n; i<=N; ++i) #define rap(i,n,N) for(int i = n; i>=N; --i) #define For(i,n,N) for(int i = n; i< N; ++i) #define endl '\n' #define pb push_back #define all(x) x.begin(),x.end() #define mems(x,y) memset(x,y,sizeof x) #define ari(x) array<int,x> #define pll pair<ll,ll> #define pii pair<int,int> #define fi first #define se second const int MAX = 1e5 + 5; mt19937 rng(time(NULL)); int n,x[MAX],y[MAX],cnt; vector<int> v; #define lc (id<<1) #define rc ((id<<1)|1) struct Segtree{ int tree[1<<18]; int n,val,a,b; void build(int id,int le,int ri){ if(le==ri){ tree[id] = x[le]; return; } int mid = le+ri>>1; build(lc,le,mid), build(rc,mid+1,ri); tree[id] = max(tree[lc], tree[rc]); return; } int que(int id,int le,int ri){ if(le>b || ri<a)return 0; if(le>=a && ri<=b)return tree[id]; int mid = le+ri>>1; return max(que(lc,le,mid), que(rc,mid+1,ri)); } int que(int L,int R){ a = L, b = R; return que(1,1,n); } void upd(int id,int le,int ri){ if(le==ri){ tree[id] = val; return; } int mid = le+ri>>1; if(a<=mid)upd(lc,le,mid); else upd(rc,mid+1,ri); tree[id] = max(tree[lc], tree[rc]); return; } void upd(int pos,int _v){ a = pos; val = _v; upd(1,1,n); } }rmq, tree; vector<int> z[MAX]; int main(){ // freopen("input.4_j", "r", stdin); ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n; rep(i,1,n)cin>>x[i], v.pb(x[i]); sort(all(v)); v.erase(unique(all(v)), v.end()); rep(i,1,n)x[i] = upper_bound(all(v), x[i]) - v.begin(); auto it = v.begin(); rep(i,1,n){ cin>>y[i]; it = lower_bound(all(v), y[i]); y[i] = it==v.end() || *it!=y[i] ? 0 : it-v.begin()+1; } rmq.n = tree.n = n; rmq.build(1,1,n); rep(i,1,n)z[x[i]].pb(i); int pos,val; rep(i,1,n){ if(x[i]<=y[i]){ it = lower_bound(all(z[y[i]]), i); pos = -1; if(it != z[y[i]].end()){ pos = *it; if(rmq.que(i,pos)==y[i])tree.upd(pos, tree.que(1,pos) + 1); } if(pos != i && it != z[y[i]].begin()){ pos = *prev(it); if(rmq.que(pos, i)==y[i])tree.upd(pos, tree.que(1, pos) + 1); } } } cout<<tree.tree[1]<<endl; return 0; }

Compilation message (stderr)

exam.cpp: In member function 'void Segtree::build(int, int, int)':
exam.cpp:37:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   37 |   int mid = le+ri>>1;
      |             ~~^~~
exam.cpp: In member function 'int Segtree::que(int, int, int)':
exam.cpp:45:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |   int mid = le+ri>>1;
      |             ~~^~~
exam.cpp: In member function 'void Segtree::upd(int, int, int)':
exam.cpp:57:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |   int mid = le+ri>>1;
      |             ~~^~~
exam.cpp: In function 'int main()':
exam.cpp:90:10: warning: unused variable 'val' [-Wunused-variable]
   90 |  int pos,val;
      |          ^~~
#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...