#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include "bits_stdc++.h"
#define endl '\n'
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define input(x) scanf("%d", &x);
#define input2(x, y) scanf("%lld%lld", &x, &y);
#define input3(x, y, z) scanf("%lld%lld%lld", &x, &y, &z);
#define input4(x, y, z, a) scanf("%lld%lld%lld%lld", &x, &y, &z, &a);
#define print(x, y) printf("%lld%c", x, y);
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define all(x) x.begin(), x.end()
#define discretize(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
using namespace std;
//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
//#define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
typedef long long ll;
typedef __int128 sll;
typedef long double ld;
typedef pair<ld, ll> pd;
typedef pair<string, ll> psl;
typedef pair<ll, ll> pi;
typedef pair<ll, pi> pii;
typedef pair<pi, pi> piii;
ll n, arr[200005];
long long ans = 0;
vector<ll> dis;
vector<ll> dish[200005];
inline ll summation(ll x, ll y)
{
ll val = 0;
if (x>=0)
{
val = y*(y+1)/2 - (x-1)*(x)/2;
}
else if (y<=0)
{
x = -x, y = -y;
val = (x-1)*(x)/2 - y*(y+1)/2;
}
else
{
val = y*(y+1)/2 - abs(x)*(abs(x)+1)/2;
}
//show3(x,y, val);
return val;
}
struct node{
int s, e, m;
ll counter;
ll summ;
int lazy;
node *l, *r;
node (int S, int E)
{
s = S, e = E, m = s+e;
if (m>=0) m/=2;
else m = (m-1)/2;
counter =0, summ = 0;
lazy = 0;
l=r=nullptr;
}
void create()
{
if(s != e && l==nullptr)
{
l = new node(s, m);
r = new node(m+1, e);
}
}
void propogate()
{
if (lazy==0) return;
counter += lazy;
summ += summation(s, e)*lazy;
create();
if (s != e){
l->lazy+=lazy;
r->lazy+=lazy;
}
lazy=0;
}
void update(int S, int E, ll V)
{
propogate();
if(s==S && e==E) {lazy += V; return;}
else{
create();
if(E <= m) l->update(S, E, V);
else if (m < S) r->update(S, E, V);
else l->update(S, m, V),r->update(m+1, E, V);
l->propogate(),r->propogate();
counter = l->counter + r->counter;
summ = l-> summ + r->summ;
}
}
ll querycount(int S, int E)
{
propogate();
if(s == S && e == E) return counter;
create();
if(E <= m) return l->querycount(S, E);
else if(S >= m+1) return r->querycount(S, E);
else return l->querycount(S, m) + r->querycount(m+1, E);
}
ll querysum(int S, int E)
{
propogate();
if(s == S && e == E) return summ;
create();
if(E <= m) return l->querysum(S, E);
else if(S >= m+1) return r->querysum(S, E);
else return l->querysum(S, m) + r->querysum(m+1, E);
}
} *root;
int main()
{
input(n);
for (ll i=0; i<n; ++i)
{
input(arr[i]);
dis.pb(arr[i]);
}
discretize(dis);
for (ll i=0; i<n; ++i)
{
ll ind = lb(all(dis), arr[i])-dis.begin();
dish[ind].pb(i);
}
root = new node(-n-5, n+5);
for (ll i=0; i<dis.size(); ++i)
{
//show(i);
ll offset = 0;
root = new node(-n-5, n+5);
vector<ll> & now = dish[i];
vector<pi> log;
for (ll j=0; j<now.size(); ++j)
{
ll start;
if (j) start = now[j-1] + 1;
else start = 0;
ll len = now[j]-start;
//show(len);
if (len>=1) {root->update(offset, offset+len-1, 1);log.pb(mp(offset, offset+len-1));}
offset += len;
root->update(offset, offset, 1);
log.pb(mp(offset, offset));
offset--;
//show(offset);
ll end;
if (j+1<now.size()) end = now[j+1] -1;
else end = n-1;
len = end-now[j]+1;
//show(len);
//show2( root->querysum(offset+1, offset+len), root->querycount(offset+1, offset+len));
ans += root->querysum(offset+1, offset+len) - offset*root->querycount(offset+1, offset+len);
//show(ans);
if (offset+len+1<=n+1) ans += root->querycount(offset+len+1, n+1)*len;
//show(ans);
}
for (pi u: log) root->update(u.f, u.s, -1);
}
print(ans, '\n');
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'int main()':
Main.cpp:12:24: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll*' {aka 'long long int*'} [-Wformat=]
12 | #define input(x) scanf("%d", &x);
| ^~~~
Main.cpp:139:9: note: in expansion of macro 'input'
139 | input(n);
| ^~~~~
Main.cpp:12:26: note: format string is defined here
12 | #define input(x) scanf("%d", &x);
| ~^
| |
| int*
| %lld
Main.cpp:12:24: warning: format '%d' expects argument of type 'int*', but argument 2 has type 'll*' {aka 'long long int*'} [-Wformat=]
12 | #define input(x) scanf("%d", &x);
| ^~~~
Main.cpp:142:17: note: in expansion of macro 'input'
142 | input(arr[i]);
| ^~~~~
Main.cpp:12:26: note: format string is defined here
12 | #define input(x) scanf("%d", &x);
| ~^
| |
| int*
| %lld
Main.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | #define input(x) scanf("%d", &x);
| ~~~~~^~~~~~~~~~
Main.cpp:139:9: note: in expansion of macro 'input'
139 | input(n);
| ^~~~~
Main.cpp:12:23: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | #define input(x) scanf("%d", &x);
| ~~~~~^~~~~~~~~~
Main.cpp:142:17: note: in expansion of macro 'input'
142 | input(arr[i]);
| ^~~~~| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
