oj.uz

답안 #535205

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
535205 2022-03-09T16:54:16 Z NaimSS 케이크 (CEOI14_cake) C++14
0 / 100
 2000 ms 22328 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,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: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:162:21: note: in expansion of macro 'dbg'
  162 |       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:166:7: note: in expansion of macro 'dbg'
  166 |       dbg(ini[i]);
      |       ^~~
cake.cpp:50:18: warning: statement has no effect [-Wunused-value]
   50 | #define dbg(...) 42
      |                  ^~
cake.cpp:170:7: note: in expansion of macro 'dbg'
  170 |       dbg(id[i],nxt[i]);
      |       ^~~
cake.cpp:50:18: warning: statement has no effect [-Wunused-value]
   50 | #define dbg(...) 42
      |                  ^~
cake.cpp:178:9: note: in expansion of macro 'dbg'
  178 |         dbg(b[i],mx,l);
      |         ^~~
cake.cpp:50:18: warning: statement has no effect [-Wunused-value]
   50 | #define dbg(...) 42
      |                  ^~
cake.cpp:183:9: note: in expansion of macro 'dbg'
  183 |         dbg(b[i],mx,r);
      |         ^~~

Subtask #1
0 / 15.0

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

Subtask #2
0.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 166 ms 12364 KB Output isn't correct
2 Incorrect 121 ms 11076 KB Output isn't correct
3 Incorrect 153 ms 12188 KB Output isn't correct
4 Incorrect 135 ms 11320 KB Output isn't correct
5 Incorrect 182 ms 11716 KB Output isn't correct
6 Incorrect 169 ms 11992 KB Output isn't correct
7 Incorrect 169 ms 11852 KB Output isn't correct
8 Incorrect 137 ms 12104 KB Output isn't correct

Subtask #3
0.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 288 ms 5764 KB Output isn't correct
2 Incorrect 138 ms 5604 KB Output isn't correct
3 Incorrect 50 ms 4896 KB Output isn't correct
4 Correct 1 ms 332 KB Output is correct
5 Execution timed out 2045 ms 8860 KB Time limit exceeded
6 Incorrect 1174 ms 8864 KB Output isn't correct
7 Incorrect 276 ms 8336 KB Output isn't correct

Subtask #4
0.0 / 50.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 22 ms 1828 KB Output isn't correct
2 Incorrect 23 ms 1768 KB Output isn't correct
3 Incorrect 48 ms 3964 KB Output isn't correct
4 Incorrect 68 ms 3932 KB Output isn't correct
5 Incorrect 70 ms 4200 KB Output isn't correct
6 Incorrect 718 ms 6412 KB Output isn't correct
7 Incorrect 174 ms 5956 KB Output isn't correct
8 Incorrect 96 ms 8656 KB Output isn't correct
9 Incorrect 367 ms 22328 KB Output isn't correct
10 Incorrect 177 ms 12192 KB Output isn't correct
11 Incorrect 681 ms 14216 KB Output isn't correct
12 Execution timed out 2012 ms 19900 KB Time limit exceeded
13 Execution timed out 2007 ms 21308 KB Time limit exceeded