| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 549471 |
2022-04-15T21:26:02 Z |
duality |
Fish 2 (JOI22_fish2) |
C++17 |
|
856 ms |
157596 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];
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],lazy[1 << 18],occ[1 << 18];
int build(int s,int e,int i) {
if (s == e) {
occ[i] = 1;
return 0;
}
int mid = (s+e) / 2;
build(s,mid,2*i+1),build(mid+1,e,2*i+2);
occ[i] = e-s+1;
return 0;
}
int prop(int s,int e,int i) {
if (lazy[i] != 0) {
tree[i] += lazy[i];
if (s != e) lazy[2*i+1] += lazy[i],lazy[2*i+2] += lazy[i];
lazy[i] = 0;
}
return 0;
}
vector<pair<pii,int> > updates;
int update(int s,int e,int as,int ae,int i,int num) {
if (i == 0) updates.pb(mp(mp(as,ae),num));
prop(s,e,i);
if ((s > ae) || (e < as)) return 0;
else if ((s >= as) && (e <= ae)) {
lazy[i] += num;
prop(s,e,i);
return 0;
}
int mid = (s+e) / 2;
update(s,mid,as,ae,2*i+1,num),update(mid+1,e,as,ae,2*i+2,num);
tree[i] = min(tree[2*i+1],tree[2*i+2]),occ[i] = 0;
if (tree[i] == tree[2*i+1]) occ[i] += occ[2*i+1];
if (tree[i] == tree[2*i+2]) occ[i] += occ[2*i+2];
return 0;
}
pii query(int s,int e,int qs,int qe,int i) {
prop(s,e,i);
if ((s > qe) || (e < qs)) return mp(1e9,0);
else if ((s >= qs) && (e <= qe)) return mp(tree[i],occ[i]);
int mid = (s+e) / 2;
pii l = query(s,mid,qs,qe,2*i+1),r = query(mid+1,e,qs,qe,2*i+2);
return mp(min(l.first,r.first),((l.first <= r.first) ? l.second:0)+((l.first >= r.first) ? r.second:0));
}
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);
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);
}
build(0,N-1,0);
for (i = 0; i < N; i++) update(i,A[i]);
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);
if (T == 1) scanf("%d %d",&X,&Y),update2(X,Y,1),updates.clear();
else {
scanf("%d %d",&L,&R);
int l = A[L-1],r = A[R+1];
update2(L-1,1.1e9,1),update2(R+1,1.1e9,1);
pii p = query(0,N-1,L,R,0);
printf("%d\n",p.second);
for (auto [p,n]: updates) update(0,N-1,p.first,p.second,0,-n);
updates.clear();
update2(L-1,l,-1),update2(R+1,r,-1);
}
}
return 0;
}
Compilation message
fish2.cpp: In function 'int main()':
fish2.cpp:161:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
161 | scanf("%d",&N);
| ~~~~~^~~~~~~~~
fish2.cpp:162:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
162 | for (i = 1; i <= N; i++) scanf("%d",&A[i]);
| ~~~~~^~~~~~~~~~~~
fish2.cpp:183:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
183 | scanf("%d",&Q);
| ~~~~~^~~~~~~~~
fish2.cpp:185:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
185 | scanf("%d",&T);
| ~~~~~^~~~~~~~~
fish2.cpp:186:26: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
186 | if (T == 1) scanf("%d %d",&X,&Y),update2(X,Y,1),updates.clear();
| ~~~~~^~~~~~~~~~~~~~~
fish2.cpp:188:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
188 | scanf("%d %d",&L,&R);
| ~~~~~^~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Runtime error |
856 ms |
157596 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Runtime error |
856 ms |
157596 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Runtime error |
856 ms |
157596 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
