| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 549490 |
2022-04-15T22:47:15 Z |
duality |
Fish 2 (JOI22_fish2) |
C++17 |
|
0 ms |
0 KB |
#define DEBUG 0
#include <bits/stdc++.h>
using namespace std;
#if DEBUG
// basic debugging macros
int __i__,__j__;
#define printLine(l) for(__i__=0;__i__<l;__i__++){cout<<"-";}cout<<endl
#define printLine2(l,c) for(__i__=0;__i__<l;__i__++){cout<<c;}cout<<endl
#define printVar(n) cout<<#n<<": "<<n<<endl
#define printArr(a,l) cout<<#a<<": ";for(__i__=0;__i__<l;__i__++){cout<<a[__i__]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<a[__i__][__j__]<<" ";}cout<<endl;}
#define print2dArr2(a,r,c,l) cout<<#a<<":\n";for(__i__=0;__i__<r;__i__++){for(__j__=0;__j__<c;__j__++){cout<<setw(l)<<setfill(' ')<<a[__i__][__j__]<<" ";}cout<<endl;}
// advanced debugging class
// debug 1,2,'A',"test";
class _Debug {
public:
template<typename T>
_Debug& operator,(T val) {
cout << val << endl;
return *this;
}
};
#define debug _Debug(),
#else
#define printLine(l)
#define printLine2(l,c)
#define printVar(n)
#define printArr(a,l)
#define print2dArr(a,r,c)
#define print2dArr2(a,r,c,l)
#define debug
#endif
// define
#define MAX_VAL 999999999
#define MAX_VAL_2 999999999999999999LL
#define EPS 1e-6
#define mp make_pair
#define pb push_back
// typedef
typedef unsigned int UI;
typedef long long int LLI;
typedef unsigned long long int ULLI;
typedef unsigned short int US;
typedef pair<int,int> pii;
typedef pair<LLI,LLI> plli;
typedef vector<int> vi;
typedef vector<LLI> vlli;
typedef vector<pii> vpii;
typedef vector<plli> vplli;
// ---------- END OF TEMPLATE ----------
#pragma GCC optimize("Ofast")
int N,A[100002];
LLI bit[100003],bit2[100003];
int update(int i,int num) {
for (i++; i <= N; i += i & (-i)) bit[i] += num;
return 0;
}
LLI query(int s,int e) {
LLI sum = 0;
for (e++; e > 0; e -= e & (-e)) sum += bit[e];
for (; s > 0; s -= s & (-s)) sum -= bit[s];
return sum;
}
set<int> layer[31];
int tree[1 << 18],pre[1 << 18],occ[1 << 18];
int build(int s,int e,int i) {
if (s == e) {
occ[i] = 1,tree[i] = pre[i] = 0;
return 0;
}
int mid = (s+e) / 2;
build(s,mid,2*i),build(mid+1,e,2*i+1);
tree[i] = tree[2*i]+tree[2*i+1];
pre[i] = min(pre[2*i],tree[2*i]+pre[2*i+1]);
occ[i] = 0;
if (pre[i] == pre[2*i]) occ[i] += occ[2*i];
if (pre[i] == tree[2*i]+pre[2*i+1]) occ[i] += occ[2*i+1];
return 0;
}
int update3(int i,int num) {
int u = i+(1 << 17);
tree[u] += num,pre[u] += num;
while (u >= (1 << 8)) {
u >>= 1;
tree[u] = tree[u << 1]+tree[(u << 1)|1];
pre[u] = min(pre[u << 1],tree[u << 1]+pre[(u << 1)|1]);
occ[u] = ((pre[u] == pre[u << 1]) ? occ[u << 1]:0):((pre[u] == tree[u << 1]+pre[(u << 1)|1]) ? occ[(u << 1)|1]:0);
}
return 0;
}
int arr[1000];
int f = 0;
int toadd[1 << 17],done[1 << 17];
vi all;
int update(int s,int e,int as,int ae,int i,int num) {
if (f == 1) toadd[as] += num,toadd[ae+1] -= num,all.pb(as),all.pb(ae+1);
else update3(as,num),update3(ae+1,-num);
return 0;
}
pair<pii,int> query(int s,int e,int qs,int qe,int i) {
if ((s >= qs) && (e <= qe) && (i >= (1 << 8))) return mp(mp(tree[i],pre[i]),occ[i]);
int mid = (s+e) / 2;
if (qe <= mid) return query(s,mid,qs,qe,2*i);
else if (qs >= mid+1) return query(mid+1,e,qs,qe,2*i+1);
else {
auto l = query(s,mid,qs,qe,2*i),r = query(mid+1,e,qs,qe,2*i+1);
pair<pii,int> p;
p.first.first = l.first.first+r.first.first;
p.first.second = min(l.first.second,l.first.first+r.first.second);
p.second = 0;
if (p.first.second == l.first.second) p.second += l.second;
if (p.first.second == l.first.first+r.first.second) p.second += r.second;
return p;
}
}
int check(int l,int r,int m = -1) {
if ((m != -1) && ((l > m) || (r < m))) return 0;
else return (l < r-1) && (min(A[l],A[r]) > query(l+1,r-1));
}
int update2(int p,int a,int t) {
int i;
for (i = 0; i < 31; i++) {
auto it = layer[i].lower_bound(p);
if (it == layer[i].end()) continue;
if (t == 1) {
if ((it != layer[i].begin()) && check(*prev(it),*it,p)) update(0,N-1,*prev(it)+1,*it-1,0,-1);
if ((next(it) != layer[i].end()) && check(*it,*next(it),p)) update(0,N-1,*it+1,*next(it)-1,0,-1);
if ((it != layer[i].begin()) && (next(it) != layer[i].end()) && check(*prev(it),*next(it),p))
update(0,N-1,*prev(it)+1,*next(it)-1,0,-1);
if ((it != layer[i].begin()) && (prev(it) != layer[i].begin()) && check(*prev(prev(it)),*it,p))
update(0,N-1,*prev(prev(it))+1,*it-1,0,-1);
if ((next(it) != layer[i].end()) && (next(next(it)) != layer[i].end()) && check(*it,*next(next(it)),p))
update(0,N-1,*it+1,*next(next(it))-1,0,-1);
}
if (*it == p) layer[i].erase(it);
}
update(p,a-A[p]),A[p] = a;
for (i = 0; i < 31; i++) {
if (i <= __lg(A[p])) layer[i].insert(p);
auto it = layer[i].lower_bound(p);
if (it == layer[i].end()) continue;
if (t == 1) {
if ((it != layer[i].begin()) && check(*prev(it),*it,p)) update(0,N-1,*prev(it)+1,*it-1,0,1);
if ((next(it) != layer[i].end()) && check(*it,*next(it),p)) update(0,N-1,*it+1,*next(it)-1,0,1);
if ((it != layer[i].begin()) && (next(it) != layer[i].end()) && check(*prev(it),*next(it),p))
update(0,N-1,*prev(it)+1,*next(it)-1,0,1);
if ((it != layer[i].begin()) && (prev(it) != layer[i].begin()) && check(*prev(prev(it)),*it,p))
update(0,N-1,*prev(prev(it))+1,*it-1,0,1);
if ((next(it) != layer[i].end()) && (next(next(it)) != layer[i].end()) && check(*it,*next(next(it)),p))
update(0,N-1,*it+1,*next(next(it))-1,0,1);
}
}
return 0;
}
int main() {
int i;
int Q;
scanf("%d",&N);
mt19937 gen;
clock_t init = clock();
for (i = 1; i <= N; i++) scanf("%d",&A[i]);
A[0] = A[N+1] = 1.1e9,N += 2;
int j;
for (i = 0; i < N; i++) {
for (j = 0; j <= __lg(A[i]); j++) layer[j].insert(i);
}
for (i = 0; i < N; i++) update(i,A[i]);
build(0,(1 << 17)-1,1);
for (i = 0; i < 31; i++) {
for (auto it = layer[i].begin(); it != layer[i].end(); it++) {
if (it != layer[i].begin()) {
if (check(*prev(it),*it)) update(0,N-1,*prev(it)+1,*it-1,0,1);
if (next(it) != layer[i].end()) {
if (check(*prev(it),*next(it))) update(0,N-1,*prev(it)+1,*next(it)-1,0,1);
}
}
}
}
int T,X,Y,L,R;
scanf("%d",&Q);
for (i = 0; i < Q; i++) {
scanf("%d",&T);
//T = 2;
if (T == 1) {
//X = uniform_int_distribution<int>(1,N-2)(gen),Y = uniform_int_distribution<int>(1,1e9)(gen);
scanf("%d %d",&X,&Y);
update2(X,Y,1);
}
else {
scanf("%d %d",&L,&R);
if ((L == 1) && (R == N-2)) {
auto p = query(0,(1 << 17)-1,L,R,1);
printf("%d\n",p.second);
}
else {
//L = 1+(rand() % N),R = 1+(rand() % N); if (L > R) swap(L,R);
int l = A[L-1],r = A[R+1];
f = 1;
update2(L-1,1.1e9,1),update2(R+1,1.1e9,1);
f = 0;
for (int x: all) {
if (!done[x] && (toadd[x] != 0)) update3(x,toadd[x]),done[x] = 1;
}
auto p = query(0,(1 << 17)-1,L,R,1);
printf("%d\n",p.second);
update2(L-1,l,0),update2(R+1,r,0);
for (int x: all) {
if (done[x] && (toadd[x] != 0)) update3(x,-toadd[x]),done[x] = 0,toadd[x] = 0;
}
all.clear();
}
}
}
//cerr<<(double)(clock()-init)/CLOCKS_PER_SEC<<endl;
return 0;
}
Compilation message
fish2.cpp: In function 'int update3(int, int)':
fish2.cpp:95:59: error: expected ';' before ':' token
95 | occ[u] = ((pre[u] == pre[u << 1]) ? occ[u << 1]:0):((pre[u] == tree[u << 1]+pre[(u << 1)|1]) ? occ[(u << 1)|1]:0);
| ^
| ;
fish2.cpp: In function 'int main()':
fish2.cpp:170:13: warning: unused variable 'init' [-Wunused-variable]
170 | clock_t init = clock();
| ^~~~
fish2.cpp:168:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
168 | scanf("%d",&N);
| ~~~~~^~~~~~~~~
fish2.cpp:171:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
171 | for (i = 1; i <= N; i++) scanf("%d",&A[i]);
| ~~~~~^~~~~~~~~~~~
fish2.cpp:192:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
192 | scanf("%d",&Q);
| ~~~~~^~~~~~~~~
fish2.cpp:194:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
194 | scanf("%d",&T);
| ~~~~~^~~~~~~~~
fish2.cpp:198:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
198 | scanf("%d %d",&X,&Y);
| ~~~~~^~~~~~~~~~~~~~~
fish2.cpp:202:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
202 | scanf("%d %d",&L,&R);
| ~~~~~^~~~~~~~~~~~~~~
