제출 #160497

#제출 시각아이디문제언어결과실행 시간메모리
160497luciocf케이크 (CEOI14_cake)C++14
0 / 100
2076 ms31224 KiB
#include <bits/stdc++.h> using namespace std; const int maxn = 5e5+10; int n; int a[maxn]; pair<int, int> aux[maxn]; map<int, int> pos; int tree[4*maxn]; vector<pair<int, int>> mx; void faz(void) { sort(aux+1, aux+n+1); for (int i = max(1, n-12); i <= n; i++) mx.push_back({a[aux[i].second], aux[i].second}); } void build(int node, int l, int r) { if (l == r) { tree[node] = a[l]; return; } int mid = (l+r)>>1; build(2*node, l, mid); build(2*node+1, mid+1, r); tree[node] = max(tree[2*node], tree[2*node+1]); } void upd(int node, int l, int r, int pos, int v) { if (l == r) { tree[node] = v; return; } int mid = (l+r)>>1; if (pos <= mid) upd(2*node, l, mid, pos, v); else upd(2*node+1, mid+1, r, pos, v); tree[node] = max(tree[2*node], tree[2*node+1]); } int query(int node, int l, int r, int a, int b) { if (l > b || r < a) return -1; if (l >= a && r <= b) return tree[node]; int mid = (l+r)>>1; return max(query(2*node, l, mid, a, b), query(2*node+1, mid+1, r, a, b)); } int findL(int node, int l, int r, int pos, int v) { if (l > pos || tree[node] <= v) return -1; if (l == r) return l; int mid = (l+r)>>1; int p1 = findL(2*node+1, mid+1, r, pos, v); return (p1 == -1 ? findL(2*node, l, mid, pos, v) : p1); } int findR(int node, int l, int r, int pos, int v) { if (r < pos || tree[node] <= v) return -1; if (l == r) return l; int mid = (l+r)>>1; int p1 = findR(2*node, l, mid, pos, v); return (p1 == -1 ? findR(2*node+1, mid+1, r, pos, v) : p1); } int main(void) { int A; scanf("%d %d", &n, &A); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); aux[i] = {a[i], i}, pos[a[i]] = i; } faz(); build(1, 1, n); int q; scanf("%d", &q); for (int t = 1; t <= q; t++) { char op; scanf(" %c", &op); if (op == 'E') { int ind, e; scanf("%d %d", &ind, &e); vector<pair<int, int>> aux; a[ind] = mx[mx.size()-e].first; pos[a[ind]] = ind; int qtd = 0; for (int i = mx.size()-1; i > mx.size()-e; i--, qtd++) aux.push_back(mx[i]); aux.push_back({a[ind], ind}), ++qtd; for (int i = mx.size()-e; i >= 0 && qtd < 13; i--, qtd++) aux.push_back(mx[i]); mx.clear(); for (int i = aux.size()-1; i >= 0; i--) mx.push_back(aux[i]); for (int i = 1; i < mx.size(); i++) { if (mx[i].first == mx[i-1].first) { a[mx[i].second]++; mx[i].first++; } } for (int i = 0; i < mx.size(); i++) { upd(1, 1, n, mx[i].second, mx[i].first); pos[mx[i].first] = mx[i].second; } } else { int ind; scanf("%d", &ind); if (ind == A) printf("0\n"); else if (ind < A) { int M = query(1, 1, n, ind, A-1); int p = pos[M], last = findR(1, 1, n, A+1, M); if (last == -1) printf("%d\n", n-ind); else printf("%d\n", last-ind-1); } else { int M = query(1, 1, n, A+1, ind); int p = pos[M], last = findL(1, 1, n, A-1, M); if (last == -1) printf("%d\n", ind-1); else printf("%d\n", ind-last-1); } } } }

컴파일 시 표준 에러 (stderr) 메시지

cake.cpp: In function 'int main()':
cake.cpp:124:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = mx.size()-1; i > mx.size()-e; i--, qtd++)
                              ~~^~~~~~~~~~~~~
cake.cpp:137:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 1; i < mx.size(); i++)
                    ~~^~~~~~~~~~~
cake.cpp:146:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for (int i = 0; i < mx.size(); i++)
                    ~~^~~~~~~~~~~
cake.cpp:162:9: warning: unused variable 'p' [-Wunused-variable]
     int p = pos[M], last = findR(1, 1, n, A+1, M);
         ^
cake.cpp:172:9: warning: unused variable 'p' [-Wunused-variable]
     int p = pos[M], last = findL(1, 1, n, A-1, M);
         ^
cake.cpp:92:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &A);
  ~~~~~^~~~~~~~~~~~~~~~~
cake.cpp:96:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
cake.cpp:105:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &q);
  ~~~~~^~~~~~~~~~
cake.cpp:110:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c", &op);
   ~~~~~^~~~~~~~~~~~
cake.cpp:115:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d", &ind, &e);
    ~~~~~^~~~~~~~~~~~~~~~~~~
cake.cpp:156:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &ind);
    ~~~~~^~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...