oj.uz

답안 #535209

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
535209 2022-03-09T16:58:06 Z NaimSS 케이크 (CEOI14_cake) C++14
0 / 100
 2000 ms 15332 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){
  for(int k=idr;k>=1;k--){
    if(val[k] > mx)return k;
  }
  return 0;
  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){
  for(int k=idl;k<=n;k++){
    if(val[k] > mx)return k;
  }
  return n+1;
  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];
      }
    }
    
    
    rep(i,1,n+1){
      upd(1,1,n,i,ini[i]);
      val[i] = ini[i];
    }

    rep(i,1,q+1)if(op[i]=='E'){
      dbg(id[i],nxt[i]);
      val[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:150:9: note: in expansion of macro 'dbg'
  150 |         dbg(id[i],nxt[i]);
      |         ^~~
cake.cpp:50:18: warning: statement has no effect [-Wunused-value]
   50 | #define dbg(...) 42
      |                  ^~
cake.cpp:168:7: note: in expansion of macro 'dbg'
  168 |       dbg(id[i],nxt[i]);
      |       ^~~
cake.cpp:50:18: warning: statement has no effect [-Wunused-value]
   50 | #define dbg(...) 42
      |                  ^~
cake.cpp:177:9: note: in expansion of macro 'dbg'
  177 |         dbg(b[i],mx,l);
      |         ^~~
cake.cpp:50:18: warning: statement has no effect [-Wunused-value]
   50 | #define dbg(...) 42
      |                  ^~
cake.cpp:182:9: note: in expansion of macro 'dbg'
  182 |         dbg(b[i],mx,r);
      |         ^~~

Subtask #1
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Incorrect 0 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 146 ms 7752 KB Output isn't correct
2 Correct 135 ms 7896 KB Output is correct
3 Correct 130 ms 7864 KB Output is correct
4 Correct 127 ms 8248 KB Output is correct
5 Incorrect 151 ms 8232 KB Output isn't correct
6 Incorrect 146 ms 8140 KB Output isn't correct
7 Correct 148 ms 8148 KB Output is correct
8 Correct 158 ms 8284 KB Output is correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 917 ms 4552 KB Output is correct
2 Incorrect 770 ms 4084 KB Output isn't correct
3 Correct 1029 ms 3864 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Execution timed out 2089 ms 6492 KB Time limit exceeded
6 Execution timed out 2083 ms 6444 KB Time limit exceeded
7 Execution timed out 2060 ms 6128 KB Time limit exceeded

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 26 ms 1356 KB Output isn't correct
2 Correct 30 ms 1464 KB Output is correct
3 Correct 203 ms 3064 KB Output is correct
4 Incorrect 220 ms 3216 KB Output isn't correct
5 Incorrect 67 ms 3200 KB Output isn't correct
6 Correct 525 ms 4828 KB Output is correct
7 Correct 164 ms 4380 KB Output is correct
8 Correct 107 ms 6200 KB Output is correct
9 Execution timed out 2084 ms 15332 KB Time limit exceeded
10 Incorrect 211 ms 9732 KB Output isn't correct
11 Incorrect 633 ms 10500 KB Output isn't correct
12 Execution timed out 2059 ms 14576 KB Time limit exceeded
13 Execution timed out 2055 ms 15304 KB Time limit exceeded