#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
int read(){int x;scanf("%lld",&x);return x;}
void print(int x){printf("%lld\n",x);}
void file(string s)
{
freopen((s+".in").c_str(),"r",stdin);
freopen((s+".out").c_str(),"w",stdout);
}
const int mod=998244353;
int n;
int a[200005];
int nxt[200005];
int seg[200005*4],tag[200005*4];
void upd(int id){seg[id]=seg[id*2]+seg[id*2+1];}
void pushdown(int id,int l,int r)
{
int mid=(l+r)/2;
if(tag[id])
{
seg[id*2]=(mid-l+1)*tag[id];
seg[id*2+1]=(r-mid)*tag[id];
tag[id*2]=tag[id*2+1]=tag[id];
tag[id]=0;
}
}
void assign(int id,int l,int r,int ql,int qr,int x)
{
if(l==ql&&r==qr)
{
seg[id]=x*(r-l+1);
tag[id]=x;return;
}
int mid=(l+r)/2;
if(qr<=mid){assign(id*2,l,mid,ql,qr,x);}
else if(ql>mid){assign(id*2+1,mid+1,r,ql,qr,x);}
else{assign(id*2,l,mid,ql,mid,x);assign(id*2+1,mid+1,r,mid+1,qr,x);}
upd(id);
}
int query(int id,int l,int r,int x)
{
if(l==r){return seg[id];}
pushdown(id,l,r);
int mid=(l+r)/2;
if(x<=mid){return query(id*2,l,mid,x);}
return query(id*2+1,mid+1,r,x);
}
set<int> v[200005];
signed main()
{
n=read();
map<int,int> vis;
vector<int> lsh;
rep1(i,n){a[i]=read();lsh.pb(a[i]);}
sort(lsh.begin(),lsh.end());
rep1(i,n)
{
int x=a[i];
a[i]=lower_bound(lsh.begin(),lsh.end(),a[i])-lsh.begin()+1;
vis[a[i]]=x;
}
rep1(i,n)
{
if(!v[a[i]].empty())
{
//cout<<nxt[a[i]]<<" "<<i<<" "<<a[i]<<endl;
assign(1,1,n,*(--v[a[i]].end()),i,a[i]);
for(int j=*(--v[a[i]].end());j<=i;j++)
{
v[a[j]].erase(j);
}
v[a[i]].insert(i);
}
else
{
//cout<<i<<" "<<i<<" "<<a[i]<<endl;
assign(1,1,n,i,i,a[i]);
v[a[i]].insert(i);
}
}
rep1(i,n)
{
printf("%lld\n",vis[query(1,1,n,i)]);
}
return 0;
}
Compilation message
Main.cpp: In function 'long long int read()':
Main.cpp:8:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
8 | int read(){int x;scanf("%lld",&x);return x;}
| ~~~~~^~~~~~~~~~~
Main.cpp: In function 'void file(std::string)':
Main.cpp:12:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | freopen((s+".in").c_str(),"r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:13:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
13 | freopen((s+".out").c_str(),"w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
9684 KB |
Output is correct |
2 |
Correct |
4 ms |
9684 KB |
Output is correct |
3 |
Correct |
4 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9684 KB |
Output is correct |
5 |
Correct |
4 ms |
9684 KB |
Output is correct |
6 |
Correct |
5 ms |
9812 KB |
Output is correct |
7 |
Correct |
4 ms |
9684 KB |
Output is correct |
8 |
Correct |
4 ms |
9696 KB |
Output is correct |
9 |
Correct |
6 ms |
9684 KB |
Output is correct |
10 |
Correct |
5 ms |
9744 KB |
Output is correct |
11 |
Correct |
5 ms |
9812 KB |
Output is correct |
12 |
Correct |
6 ms |
9812 KB |
Output is correct |
13 |
Correct |
7 ms |
9744 KB |
Output is correct |
14 |
Correct |
5 ms |
9812 KB |
Output is correct |
15 |
Correct |
5 ms |
9812 KB |
Output is correct |
16 |
Correct |
5 ms |
9812 KB |
Output is correct |
17 |
Correct |
6 ms |
9940 KB |
Output is correct |
18 |
Correct |
6 ms |
10040 KB |
Output is correct |
19 |
Correct |
5 ms |
9812 KB |
Output is correct |
20 |
Correct |
5 ms |
9812 KB |
Output is correct |
21 |
Correct |
5 ms |
9812 KB |
Output is correct |
22 |
Correct |
5 ms |
9812 KB |
Output is correct |
23 |
Correct |
6 ms |
9812 KB |
Output is correct |
24 |
Correct |
8 ms |
9812 KB |
Output is correct |
25 |
Correct |
7 ms |
9840 KB |
Output is correct |
26 |
Correct |
5 ms |
9812 KB |
Output is correct |
27 |
Correct |
5 ms |
9812 KB |
Output is correct |
28 |
Correct |
5 ms |
9720 KB |
Output is correct |
29 |
Correct |
6 ms |
9940 KB |
Output is correct |
30 |
Correct |
10 ms |
9812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
9684 KB |
Output is correct |
2 |
Correct |
4 ms |
9684 KB |
Output is correct |
3 |
Correct |
4 ms |
9684 KB |
Output is correct |
4 |
Correct |
4 ms |
9684 KB |
Output is correct |
5 |
Correct |
5 ms |
9812 KB |
Output is correct |
6 |
Correct |
5 ms |
9684 KB |
Output is correct |
7 |
Correct |
5 ms |
9684 KB |
Output is correct |
8 |
Correct |
4 ms |
9684 KB |
Output is correct |
9 |
Correct |
5 ms |
9812 KB |
Output is correct |
10 |
Correct |
5 ms |
9784 KB |
Output is correct |
11 |
Correct |
5 ms |
9812 KB |
Output is correct |
12 |
Correct |
5 ms |
9812 KB |
Output is correct |
13 |
Correct |
5 ms |
9812 KB |
Output is correct |
14 |
Correct |
5 ms |
9812 KB |
Output is correct |
15 |
Correct |
5 ms |
9812 KB |
Output is correct |
16 |
Correct |
5 ms |
9764 KB |
Output is correct |
17 |
Correct |
85 ms |
20456 KB |
Output is correct |
18 |
Correct |
73 ms |
20924 KB |
Output is correct |
19 |
Correct |
85 ms |
21668 KB |
Output is correct |
20 |
Correct |
79 ms |
21596 KB |
Output is correct |
21 |
Correct |
92 ms |
21664 KB |
Output is correct |
22 |
Correct |
95 ms |
21656 KB |
Output is correct |
23 |
Correct |
81 ms |
21812 KB |
Output is correct |
24 |
Correct |
79 ms |
21688 KB |
Output is correct |
25 |
Correct |
79 ms |
21724 KB |
Output is correct |
26 |
Correct |
81 ms |
21756 KB |
Output is correct |
27 |
Correct |
82 ms |
21748 KB |
Output is correct |
28 |
Correct |
86 ms |
21692 KB |
Output is correct |
29 |
Correct |
74 ms |
21364 KB |
Output is correct |
30 |
Correct |
76 ms |
20836 KB |
Output is correct |
31 |
Correct |
79 ms |
20908 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
9684 KB |
Output is correct |
2 |
Correct |
4 ms |
9684 KB |
Output is correct |
3 |
Correct |
4 ms |
9684 KB |
Output is correct |
4 |
Correct |
5 ms |
9684 KB |
Output is correct |
5 |
Correct |
4 ms |
9684 KB |
Output is correct |
6 |
Correct |
5 ms |
9812 KB |
Output is correct |
7 |
Correct |
4 ms |
9684 KB |
Output is correct |
8 |
Correct |
4 ms |
9696 KB |
Output is correct |
9 |
Correct |
6 ms |
9684 KB |
Output is correct |
10 |
Correct |
5 ms |
9744 KB |
Output is correct |
11 |
Correct |
5 ms |
9812 KB |
Output is correct |
12 |
Correct |
6 ms |
9812 KB |
Output is correct |
13 |
Correct |
7 ms |
9744 KB |
Output is correct |
14 |
Correct |
5 ms |
9812 KB |
Output is correct |
15 |
Correct |
5 ms |
9812 KB |
Output is correct |
16 |
Correct |
5 ms |
9812 KB |
Output is correct |
17 |
Correct |
6 ms |
9940 KB |
Output is correct |
18 |
Correct |
6 ms |
10040 KB |
Output is correct |
19 |
Correct |
5 ms |
9812 KB |
Output is correct |
20 |
Correct |
5 ms |
9812 KB |
Output is correct |
21 |
Correct |
5 ms |
9812 KB |
Output is correct |
22 |
Correct |
5 ms |
9812 KB |
Output is correct |
23 |
Correct |
6 ms |
9812 KB |
Output is correct |
24 |
Correct |
8 ms |
9812 KB |
Output is correct |
25 |
Correct |
7 ms |
9840 KB |
Output is correct |
26 |
Correct |
5 ms |
9812 KB |
Output is correct |
27 |
Correct |
5 ms |
9812 KB |
Output is correct |
28 |
Correct |
5 ms |
9720 KB |
Output is correct |
29 |
Correct |
6 ms |
9940 KB |
Output is correct |
30 |
Correct |
10 ms |
9812 KB |
Output is correct |
31 |
Correct |
4 ms |
9684 KB |
Output is correct |
32 |
Correct |
4 ms |
9684 KB |
Output is correct |
33 |
Correct |
4 ms |
9684 KB |
Output is correct |
34 |
Correct |
4 ms |
9684 KB |
Output is correct |
35 |
Correct |
5 ms |
9812 KB |
Output is correct |
36 |
Correct |
5 ms |
9684 KB |
Output is correct |
37 |
Correct |
5 ms |
9684 KB |
Output is correct |
38 |
Correct |
4 ms |
9684 KB |
Output is correct |
39 |
Correct |
5 ms |
9812 KB |
Output is correct |
40 |
Correct |
5 ms |
9784 KB |
Output is correct |
41 |
Correct |
5 ms |
9812 KB |
Output is correct |
42 |
Correct |
5 ms |
9812 KB |
Output is correct |
43 |
Correct |
5 ms |
9812 KB |
Output is correct |
44 |
Correct |
5 ms |
9812 KB |
Output is correct |
45 |
Correct |
5 ms |
9812 KB |
Output is correct |
46 |
Correct |
5 ms |
9764 KB |
Output is correct |
47 |
Correct |
85 ms |
20456 KB |
Output is correct |
48 |
Correct |
73 ms |
20924 KB |
Output is correct |
49 |
Correct |
85 ms |
21668 KB |
Output is correct |
50 |
Correct |
79 ms |
21596 KB |
Output is correct |
51 |
Correct |
92 ms |
21664 KB |
Output is correct |
52 |
Correct |
95 ms |
21656 KB |
Output is correct |
53 |
Correct |
81 ms |
21812 KB |
Output is correct |
54 |
Correct |
79 ms |
21688 KB |
Output is correct |
55 |
Correct |
79 ms |
21724 KB |
Output is correct |
56 |
Correct |
81 ms |
21756 KB |
Output is correct |
57 |
Correct |
82 ms |
21748 KB |
Output is correct |
58 |
Correct |
86 ms |
21692 KB |
Output is correct |
59 |
Correct |
74 ms |
21364 KB |
Output is correct |
60 |
Correct |
76 ms |
20836 KB |
Output is correct |
61 |
Correct |
79 ms |
20908 KB |
Output is correct |
62 |
Correct |
95 ms |
24020 KB |
Output is correct |
63 |
Correct |
259 ms |
41040 KB |
Output is correct |
64 |
Correct |
274 ms |
40036 KB |
Output is correct |
65 |
Correct |
99 ms |
24564 KB |
Output is correct |
66 |
Correct |
92 ms |
24464 KB |
Output is correct |
67 |
Correct |
99 ms |
24852 KB |
Output is correct |
68 |
Correct |
104 ms |
24888 KB |
Output is correct |
69 |
Correct |
96 ms |
24936 KB |
Output is correct |
70 |
Correct |
96 ms |
24996 KB |
Output is correct |
71 |
Correct |
96 ms |
24988 KB |
Output is correct |
72 |
Correct |
98 ms |
23948 KB |
Output is correct |
73 |
Correct |
239 ms |
35084 KB |
Output is correct |
74 |
Execution timed out |
2065 ms |
29940 KB |
Time limit exceeded |
75 |
Halted |
0 ms |
0 KB |
- |