Submission #710045

#TimeUsernameProblemLanguageResultExecution timeMemory
710045Paul_Liao_1457Fish 2 (JOI22_fish2)C++17
8 / 100
253 ms4912 KiB
//記得跳題 #pragma GCC optimize("O3,unroll_loops") #pragma GCC target("avx2") #include<iostream> #include<array> #include<vector> #include<string> #include<algorithm> #include<set> #include<queue> #include<stack> #include<math.h> #include<map> #include<unordered_map> #include<unordered_set> #include<cstring> #include<iomanip> #include<bitset> #include<tuple> #include<random> using namespace std; #define ll long long #define FOR(i,a,b) for(int i=a;i<b;i++) #define REP(i,a,b) for(int i=a;i>=b;i--) #define INF (ll)(4e18) #define pb push_back #define mp make_pair #define AC ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define endl "\n" ll a[100005]; int t[100005], x[100005], y[100005], n, q; void sub1() { FOR(i, 0, q) { if (t[i] == 1) { a[x[i]] = y[i]; } else { int ans = 0; ll inia = a[x[i] - 1], inib = a[y[i] + 1]; a[x[i] - 1] = a[y[i] + 1] = INF; ll maxn = 0; FOR(j, x[i], y[i] + 1) { maxn = max(maxn, a[j]); } FOR(j, x[i], y[i] + 1) { int l = j - 1, r = j + 1; ll now = a[j]; while (1) { if (a[l] > now && a[r] > now) break; if (a[l] <= now) { now += a[l]; l--; } if (a[r] <= now) { now += a[r]; r++; } } if (now >= maxn) { ans++; } } cout << ans << endl; a[x[i] - 1] = inia; a[y[i] + 1] = inib; } } } ll maxn[400005]; void build(int id, int l, int r) { if (l == r) { maxn[id] = a[l]; return; } int mid = (l + r) >> 1; build(id << 1, l, mid); build(id << 1 | 1, mid + 1, r); maxn[id] = max(maxn[id << 1], maxn[id << 1 | 1]); } int ask(int id, int l, int r, int L, int R, ll x, int t) { if (maxn[id] < x) return (t ? n + 1 : 0); if (l > R || r < L) { return (t ? n + 1 : 0); } if (l == r) return l; if (L <= l && r <= R) { int mid = (l + r) >> 1; if (t) { if (maxn[id << 1] <= x) { return ask(id << 1 | 1, mid + 1, r, L, R, x, t); } else { return ask(id << 1, l, mid, L, R, x, t); } } else { if (maxn[id << 1 | 1] <= x) { return ask(id << 1, l, mid, L, R, x, t); } else { return ask(id << 1 | 1, mid + 1, r, L, R, x, t); } } } int mid = (l + r) >> 1; if (t) return min(ask(id << 1, l, mid, L, R, x, t), ask(id << 1 | 1, mid + 1, r, L, R, x, t)); else return max(ask(id << 1, l, mid, L, R, x, t), ask(id << 1 | 1, mid + 1, r, L, R, x, t)); } ll pre[100005]; void sub2() { build(1, 1, n); ll maxn = 0, ans = 0; FOR(i, 1, n+1) { maxn = max(maxn, a[i]); pre[i] = pre[i-1] + a[i]; } pre[n+1] = pre[n]; FOR(i, 1, n+1) { int l = i - 1, r = i + 1; ll now = a[i]; while (1) { int nl = ask(1, 1, n, 1, l ,now, 0), nr = ask(1, 1, n, r, n, now, 1); now += pre[l] - pre[nl]; now += pre[nr - 1] - pre[r - 1]; if (now >= maxn) { ans++; break; } if (now < a[nl] && now < a[nr]) break; if (a[nl] <= a[nr]) { if (now >= a[nl]) { now += a[nl]; l = nl - 1; l = max(0, l); } else { l = nl; } if (now >= a[nr]) { now += a[nr]; r = nr + 1; r = min(n+1, r); } else { r = nr; } } else { if (now >= a[nr]) { now += a[nr]; r = nr + 1; r = min(n+1, r); } else { r = nr; } if (now >= a[nl]) { now += a[nl]; l = nl - 1; l = max(0, l); } else { l = nl; } } } //cout << "now = " << now << endl; } cout << ans << endl; } signed main() { AC; // plz cin >> n; FOR(i, 1, n+1) cin >> a[i]; cin >> q; FOR(i, 0, q) cin >> t[i] >> x[i] >> y[i]; a[0] = a[n+1] = INF; if (n <= 0 && q <= 500) { sub1(); } else if (q == 1) { sub2(); } }

Compilation message (stderr)

fish2.cpp:2:39: warning: bad option '-funroll_loops' to pragma 'optimize' [-Wpragmas]
    2 | #pragma GCC optimize("O3,unroll_loops")
      |                                       ^
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
    3 | #pragma GCC target("avx2")
      |                          ^
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.cpp:3:26: warning: bad option '-funroll_loops' to attribute 'optimize' [-Wattributes]
fish2.
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...