답안 #535202

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
535202 2022-03-09T16:52:18 Z NaimSS 케이크 (CEOI14_cake) C++14
46.6667 / 100
2000 ms 12424 KB
#include <bits/stdc++.h>
#define ld long double
#define endl "\n"
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define pb push_back
#define mp(a,b) make_pair(a,b)
#define ms(v,x) memset(v,x,sizeof(v))
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define per(i, a, b) for(int i = b-1; i>=a ; i--)
#define trav(a, x) for(auto& a : x)
#define allin(a , x) for(auto a : x)
#define Unique(v) sort(all(v));v.erase(unique(all(v)),v.end());
#define sz(v) ((int)v.size())
using namespace std;
typedef vector<int> vi;
#define y1 abacaba
//#define left oooooopss
#define db(x) cerr << #x <<" == "<<x << endl;
#define db2(x,y) cerr<<#x <<" == "<<x<<", "<<#y<<" == "<<y<<endl;
#define db3(x,y,z) cerr << #x<<" == "<<x<<", "<<#y<<" == "<<y<<", "<<#z<<" == "<<z<<endl;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<ll> vl;
std::mt19937 rng((int) std::chrono::steady_clock::now().time_since_epoch().count());
ll cdiv(ll a, ll b) { return a/b+((a^b)>0&&a%b); } // divide a by b rounded up
ll fdiv(ll a, ll b) { return a/b-((a^b)<0&&a%b); } // divide a by b rounded down
inline ll mod(ll n, ll m ){ ll ret = n%m; if(ret < 0) ret += m; return ret; }
ll gcd(ll a, ll b){return (b == 0LL ? a : gcd(b, a%b));}
ll exp(ll b,ll e,ll m){
  b%=m;
  ll ans = 1;
  for (; e; b = b * b % m, e /= 2)
      if (e & 1) ans = ans * b % m;
  return ans;
}

// debug:
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T){ 
  cerr << ' ' << H; 
  dbg_out(T...); 
}
#ifdef LOCAL
#define dbg(...) cerr<<"(" << #__VA_ARGS__<<"):" , dbg_out(__VA_ARGS__) , cerr << endl
#else
#define dbg(...) 42
#endif
//

const int N = 500100;
int val[N];
char op[N];
int id[N],e[N],b[N];
vi top10;
int num[N],ini[N];
int nxt[N];
int last[N];

// seg:
int tree[4*N];
void upd(int no,int i,int j,int p,int v){
  if(i==j){
    tree[no] = v;
    return;
  }
  int m = (i+j)/2,l=2*no,r=2*no+1;
  if(p<=m)upd(l,i,m,p,v);
  else upd(r,m+1,j,p,v);
  tree[no] = max(tree[l],tree[r]);
}
int query(int no,int i,int j,int a,int b){
  if(i>j || i > b || j < a)return 0;
  if(a<=i && j<=b)return tree[no];
  int m = (i+j)/2,l=2*no,r=2*no+1;
  return max(query(l,i,m,a,b),query(r,m+1,j,a,b));
}
int buscaL(int no,int i,int j,int idr,int mx){
  if(i > idr)return 0;
  if(tree[no] < mx)return 0;
  if(i==j)return i;
  int m = (i+j)/2,l=2*no,r=2*no+1;
  int op1 = buscaL(r,m+1,j,idr,mx);
  if(op1!=0)return op1;
  return buscaL(l,i,m,idr,mx);
}
    int n,a;

int buscaR(int no,int i,int j,int idl,int mx){
  if(j < idl)return n+1;
  if(tree[no] < mx)return n+1;
  if(i==j)return i;
  int m = (i+j)/2,l=2*no,r=2*no+1;
  int op1 = buscaR(l,i,m,idl,mx);
  if(op1!=n+1)return op1;
  return buscaR(r,m+1,j,idl,mx);
}

int32_t main(){
    fastio;
    cin >> n >> a;
    for(int i=1;i<=n;i++){
      cin >> val[i];
      ini[i] = val[i];
      if(val[i] >= n-9)top10.pb(i);
    }
    int q;
    cin >> q;
    int mx = n;
    for(int i=1;i<=q;i++){
      cin >> op[i];
      if(op[i] == 'E'){
        cin >> id[i] >> e[i];
        sort(all(top10),[&](int i1,int i2){
          return  val[i1] > val[i2];
        });

        if(sz(top10) > min(n,10))top10.pop_back();
        
        mx += e[i];
        for(int j=0;j<e[i]-1;j++){
          
          val[top10[j]] = mx - j;
          
          if(last[top10[j]]>0)
            nxt[last[top10[j]]] = val[top10[j]];
          else
            ini[top10[j]] = val[top10[j]];
        }
        if(num[id[i]] == 0){
          ini[id[i]] = val[id[i]];
          num[id[i]]=1;
        }

        nxt[i] = mx - e[i] + 1;
        val[id[i]] = nxt[i];
        last[id[i]] = i;

        dbg(id[i],nxt[i]);

        int dentro=0;
        for(auto it : top10)if(it == id[i])dentro=1;
        if(!dentro)
          top10.pb(id[i]);
      }else{
        cin >> b[i];
        if(b[i] == a){
          cout << 0 << endl;
          continue;
        }
        int l = a-1,r=a+1;
        int qtd=1;
        while(1){

          if(l == 0){
            if(r==b[i])break;
            qtd++;
            r++;
          }else if(r==n+1){
            if(l==b[i])break;
            qtd++;
            l--;
          }else if(val[l] < val[r]){
            if(l == b[i])break;
            qtd++;
            l--;
          }else{
            if(r==b[i])break;
            qtd++;
            r++;
          }

        }
        cout << qtd << endl;

      }
    }
    return 0;
    
    rep(i,1,q+1){
      if(op[i]=='E')dbg(i,nxt[i]);
    }
    rep(i,1,n+1){
      upd(1,1,n,i,ini[i]);
      dbg(ini[i]);
    }

    rep(i,1,q+1)if(op[i]=='E'){
      dbg(id[i],nxt[i]);
      upd(1,1,n,id[i],nxt[i]);
    }else{
      if(b[i] == a){
        cout << 0 << endl;
      }else if(b[i] > a){
        int mx = query(1,1,n,a+1,b[i]);
        int l = (a == 1 ? 0 : buscaL(1,1,n,a-1,mx)) + 1;
        dbg(b[i],mx,l);
        cout << b[i]-l << endl;
      }else{
        int mx = query(1,1,n,b[i],a-1);
        int r = (a==n ? n + 1 : buscaR(1,1,n,a+1,mx)) - 1;
        dbg(b[i],mx,r);
        cout << r - b[i] << endl;
      }
    }
    // math -> gcd it all
    // Did u check N=1? Did you switch N,M?
}

Compilation message

cake.cpp: In function 'int32_t main()':
cake.cpp:50:18: warning: statement has no effect [-Wunused-value]
   50 | #define dbg(...) 42
      |                  ^~
cake.cpp:142:9: note: in expansion of macro 'dbg'
  142 |         dbg(id[i],nxt[i]);
      |         ^~~
cake.cpp:50:18: warning: statement has no effect [-Wunused-value]
   50 | #define dbg(...) 42
      |                  ^~
cake.cpp:184:21: note: in expansion of macro 'dbg'
  184 |       if(op[i]=='E')dbg(i,nxt[i]);
      |                     ^~~
cake.cpp:50:18: warning: statement has no effect [-Wunused-value]
   50 | #define dbg(...) 42
      |                  ^~
cake.cpp:188:7: note: in expansion of macro 'dbg'
  188 |       dbg(ini[i]);
      |       ^~~
cake.cpp:50:18: warning: statement has no effect [-Wunused-value]
   50 | #define dbg(...) 42
      |                  ^~
cake.cpp:192:7: note: in expansion of macro 'dbg'
  192 |       dbg(id[i],nxt[i]);
      |       ^~~
cake.cpp:50:18: warning: statement has no effect [-Wunused-value]
   50 | #define dbg(...) 42
      |                  ^~
cake.cpp:200:9: note: in expansion of macro 'dbg'
  200 |         dbg(b[i],mx,l);
      |         ^~~
cake.cpp:50:18: warning: statement has no effect [-Wunused-value]
   50 | #define dbg(...) 42
      |                  ^~
cake.cpp:205:9: note: in expansion of macro 'dbg'
  205 |         dbg(b[i],mx,r);
      |         ^~~
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 3 ms 456 KB Output is correct
5 Correct 41 ms 804 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 124 ms 9200 KB Output is correct
2 Correct 94 ms 8772 KB Output is correct
3 Correct 113 ms 9320 KB Output is correct
4 Correct 125 ms 9036 KB Output is correct
5 Correct 122 ms 9348 KB Output is correct
6 Correct 126 ms 9532 KB Output is correct
7 Correct 138 ms 9400 KB Output is correct
8 Correct 108 ms 9740 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2041 ms 2912 KB Time limit exceeded
2 Execution timed out 2032 ms 3628 KB Time limit exceeded
3 Execution timed out 2048 ms 3548 KB Time limit exceeded
4 Correct 1 ms 332 KB Output is correct
5 Execution timed out 2058 ms 3480 KB Time limit exceeded
6 Execution timed out 2053 ms 3296 KB Time limit exceeded
7 Execution timed out 2005 ms 3968 KB Time limit exceeded
# 결과 실행 시간 메모리 Grader output
1 Correct 70 ms 1720 KB Output is correct
2 Correct 82 ms 1756 KB Output is correct
3 Correct 1092 ms 3504 KB Output is correct
4 Correct 1101 ms 3480 KB Output is correct
5 Correct 116 ms 4296 KB Output is correct
6 Execution timed out 2041 ms 4776 KB Time limit exceeded
7 Correct 561 ms 5868 KB Output is correct
8 Correct 148 ms 6724 KB Output is correct
9 Execution timed out 2041 ms 6132 KB Time limit exceeded
10 Correct 372 ms 12424 KB Output is correct
11 Execution timed out 2033 ms 9672 KB Time limit exceeded
12 Execution timed out 2028 ms 5152 KB Time limit exceeded
13 Execution timed out 2035 ms 5840 KB Time limit exceeded