#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define x first
#define y second
#define pii pair<int, int>
#define p3i pair<pii, int>
#define pll pair<ll, ll>
#define p3l pair<pll, ll>
#define lseg L, (L+R)/2, N*2+1
#define rseg (L+R)/2+1, R, N*2+2
#define ub upper_bound
#define lb lower_bound
#define pq priority_queue
#define MN 1000000007
#define fox(k, x) for (int k=0; k<x; ++k)
#define fox1(k, x) for (int k=1; k<=x; ++k)
#define foxr(k, x) for (int k=x-1; k>=0; --k)
#define fox1r(k, x) for (int k=x; k>0; --k)
#define ms multiset
#define flood(x) memset(x, 0x3f3f3f3f, sizeof x)
#define drain(x) memset(x, 0, sizeof x)
#define rng() (rand() >> 3)*rand()
int n, a[300005], t[300005], p[300005], gl, gr, x, y, seg[1200005];
vector<pii> v, w;
vector<int> adj[300005];
bool u, b[300005];
void dfs(int N, int V){
p[N]=V;
fox(l, adj[N].size())
dfs(adj[N][l], V);
}
set<pii> s;
void add(int L, int R, int N){
if (L>gl || R<gl) return;
if (L==R){
seg[N]=x;
return;
}
add(lseg); add(rseg);
seg[N]=max(seg[N*2+1], seg[N*2+2]);
//cout << L << ' ' <<R << ' ' << seg[N] << endl;
}
int query(int L, int R, int N){
if (seg[N]<=x) return (1 << 30);
if (L==R) return L;
return min(query(lseg), query(rseg));
}
int main(){
scanf("%i", &n);
fox(l, n){
scanf("%i", &a[l]);
if (a[l]>0){
t[l]=a[l];
a[l]=0;
}
a[l]=-a[l];
}
foxr(l, n){
u=1;
while(1){
x=a[l];
//if (x==0) cout << "*";
gl=query(0, n-1, 0);
if (gl==(1 << 30) || !(v.empty() || v.back().x<=a[l]) && gl>v.back().y) break;
x=0;
add(0, n-1, 0);
adj[l].pb(gl);
//cout << "*";
}
if (!v.empty() && v.back().x>a[l]){
adj[l].pb(v.back().y);
u=0;
v.pop_back();
}
if (a[l]!=0){
if (u){
v.pb(mp(a[l], l));
} else {
//cout << "*";
gl=l; x=a[l];
add(0, n-1, 0);
}
}
//cout << a[l] << ' ' << endl;
//if (v.size())cout << v.back().y << ' ';
}
//cout << endl;-
fox(l, n){
if (t[l]!=0){
dfs(l, l);
}
}
s.insert(mp(-1, 0));
fox(l, n){
if (b[p[l]]){
s.erase(mp(p[l], t[p[l]]));
} else {
s.insert(mp(p[l], t[p[l]]));
}
b[p[l]]=!b[p[l]];
//cout << p[l] << ' ';
printf("%i\n", (--s.end())->y);
}
return 0;
}
Compilation message
edi.cpp: In function 'void dfs(int, int)':
edi.cpp:18:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
#define fox(k, x) for (int k=0; k<x; ++k)
^
edi.cpp:33:5: note: in expansion of macro 'fox'
fox(l, adj[N].size())
^
edi.cpp: In function 'int main()':
edi.cpp:68:67: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
if (gl==(1 << 30) || !(v.empty() || v.back().x<=a[l]) && gl>v.back().y) break;
^
edi.cpp:53:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i", &n);
^
edi.cpp:55:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%i", &a[l]);
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
17548 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
139 ms |
22300 KB |
Output is correct |
2 |
Correct |
146 ms |
22300 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
156 ms |
22432 KB |
Output is correct |
2 |
Correct |
143 ms |
25996 KB |
Output is correct |
3 |
Correct |
169 ms |
26188 KB |
Output is correct |
4 |
Correct |
136 ms |
22300 KB |
Output is correct |
5 |
Correct |
203 ms |
25204 KB |
Output is correct |
6 |
Correct |
79 ms |
22300 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
0 ms |
17548 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |