Submission #1045432

#	Time	Username	Problem	Language	Result	Execution time	Memory
1045432		Requiem	Growing Trees (BOI11_grow)	C++17	100 / 100	261 ms	17232 KiB

grow

#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "grow"
using namespace std;

/**Debugging Tool  **/
void __print(int x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}

template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}

void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}

#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

/*----------------------------------*/

/**  Vector nhieu chieu **/
template<int D, typename T>
struct Vec: public vector<Vec<D - 1, T>>{
     static_assert(D >= 1, "vector dimensions must be greater than 0");
     template<typename... Args>
     Vec(int n = 0, Args... args): vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...)){
     }
};

template<typename T>
struct Vec<1, T>: public vector<T> {
    Vec(int n = 0, const T& val = T()): vector<T>(n, val) {};
};
/*--------------------------------*/

template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;

const int MAXN = 3e5 + 9;

struct Question{
    char type;
    int l, r;
    int c, h;
} Query[MAXN];

int n, q;
int a[MAXN];

/**
 * Sort mang a tang dan,
 * Ta co nhan xet, khi ta tang ci thang nho nhat.
 *
 * Nếu ta tăng không cẩn thận thì thứ tự tăng dần có thể không được đảm bảo
 * Ta để ý rằng. Giả sử ta đang xét tăng đoạn [l, r] lên gọi mx[l, r] là giá trị lớn nhất được tăng
 * trong đoạn [l,r], nếu Gọi end là vị trí cuối cùng chứa số mx trong dãy, Nếu end == r thì cập nhật sẽ không làm
 * thay đổi thứ tự, Ngược lại nếu lúc này ta cập nhật ngay thì thứ tự sẽ bị thay đổi. Thế nên, gọi CntUpd là số
 * lượng phần tử max được cập, ta sẽ cập nhật cntUpd vị trí kể từ end trở xuống lúc này thứ tự sẽ không bị thay đổi.
 *
 * Với truy vấn loại F l r
 *
 * Ta tìm vị trí cuối cùng mang số gì.
 * Bao nhiêu thằng lớn nhất được cập nhật, walk on segment tree
 * Ta tìm được vị trí đó là startMx. Ta tiến hành cập nhật với các vị trí [l, startMx].
 * Sau đó ta tìm vị trí cuối cùng chứa số r rồi cập nhật từ đót trở đi.
 *
 * Truy vấn loại C:
 * walk on segment tree.
  */

void input(){
     cin >> n >> q;
     for(int i = 1; i <= n; i++){
         cin >> a[i];
     }
     sort(a + 1, a + 1 + n);
     for(int i = 1; i <= q; i++){
         cin >> Query[i].type >> Query[i].l >> Query[i].r;
         if (Query[i].type == 'F') Query[i].c = Query[i].l, Query[i].h = Query[i].r;
     }
}

struct ITnode{
    int sum = 0, lazy = 0, minRange = 0;
} IT[MAXN << 2];

void mergeNode(ITnode &res, ITnode a, ITnode b){
    res.sum = (a.sum + b.sum);
    res.minRange = min(a.minRange, b.minRange);
}
void fix(int nn, int l, int r){
    IT[nn].sum += IT[nn].lazy * (r - l + 1);
    IT[nn].minRange += IT[nn].lazy;
    if (l != r){
        IT[nn << 1].lazy += IT[nn].lazy;
        IT[nn << 1 | 1].lazy += IT[nn].lazy;
    }
    IT[nn].lazy = 0;
}

void updateRange(int nn, int l, int r, int u, int v, int k){  //Cap nhat mot doan
    fix(nn, l, r);
//    debug(nn, l, r);
    if (l >= u and r <= v){  /*debug(u, v, k);*/ IT[nn].lazy += k;  fix(nn, l, r); return; }
    if (l > v or r < u) return ;

    int mid = (l + r) >> 1;
    updateRange(nn << 1, l, mid, u, v, k);
    updateRange(nn << 1 | 1, mid + 1, r, u, v, k);
    mergeNode(IT[nn], IT[nn << 1], IT[nn << 1 | 1]);
//    debug(nn, l, r, IT[nn].minRange);
}

void getRange(int nn, int l, int r, int u, int v, ITnode &res){
    fix(nn, l, r);
    if (l >= u and r <= v){ mergeNode(res, res, IT[nn]); /*debug(IT[nn].minRange, res.sum, res.minRange);*/ return; }
    if (l > v or r < u) return;

    int mid = (l + r) >> 1;
    getRange(nn << 1, l, mid, u, v, res);
    getRange(nn << 1 | 1, mid + 1, r, u, v, res);
}

int findLastLower(int nn, int l, int r, int u, int v, int k){ //tim vi tri cuoi cung trong doan [l, r] co gia tri be hon k
    fix(nn, l, r);
    int mid = (l + r) >> 1;
    if (l > v or r < u) return 0;
    if (l >= u and r <= v){
//        debug(nn, l, r, IT[nn].minRange, k);
        if (IT[nn].minRange >= k) return 0;
        if (l == r) return l;
        fix(nn << 1, l, mid);
        fix(nn << 1 | 1, mid + 1, r);
        if (IT[nn << 1 | 1].minRange < k) return findLastLower(nn << 1 | 1, mid + 1, r, u, v, k);
        else return findLastLower(nn << 1, l, mid, u, v, k);
    }

    int g1 = findLastLower(nn << 1, l, mid, u, v, k);
    int g2 = findLastLower(nn << 1 | 1, mid + 1, r, u, v, k);

    return ((!g2) ? g1 : g2);
}

void updateRange(int u, int v, int k){
    if (u > v) return;
    updateRange(1, 1, n, u, v, k);
}

int findLastLower(int u, int v, int k){
    if (u > v) return 0;
    return findLastLower(1, 1, n, u, v, k);
}

ITnode getRange(int u, int v){
    ITnode res = {0, 0, (int) inf};
    if (u > v) return res;
    getRange(1, 1, n, u, v, res);
    return res;
}
void solve(){

     for(int i = 1; i <= n; i++){
         updateRange(1, 1, n, i, i, a[i]);
//         cerr << a[i] << ' ';
     }
//     cerr << endl;

//     cout << getRange(1, 3).minRange << endl;

     for(int i = 1; i <= q; i++){
         if (Query[i].type == 'F'){
             int start = min(n + 1, findLastLower(1, n, Query[i].h) + 1);
//
             int ending = min(n, start + Query[i].c - 1);
//             debug(start, ending);

             if (start <= ending){
                 int curEnd = getRange(ending, ending).sum;

                 int backward = findLastLower(start, ending, curEnd);
//                 debug(curEnd, backward);

                 if (backward != 0){
    //                 cerr << "UPDATE: " << 1 << endl;
                     updateRange(start, backward, 1);
//                     debug(start, backward);
                 }
                 if (backward == 0) backward = start - 1;

                 int numMax = ending - backward;
                 int last = findLastLower(1, n, curEnd + 1);
    //             cerr << "UPDATE: " << 2 << endl;
//                 debug(last - numMax + 1, last);
                 updateRange(last - numMax + 1, last, 1);

             }
         }

         else{
             int l = Query[i].l;
             int r = Query[i].r;
             int start = findLastLower(1, n, l) + 1;
             int ending = findLastLower(1, n, r + 1);
//             debug(start, ending);
             cout << ending - start + 1 << endl;
         }
     }
}
main()
{
    fast;
    if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
    }
    input();
    solve();


}
/**
Warning:
- MLE / TLE?
- Gioi han mang?
- Gia tri max phai luon gan cho -INF
- long long co can thiet khong?
- tran mang.
- code can than hon
- Nho sinh test de tranh RTE / TLE

--> Coi lai truoc khi nop
**/

Compilation message (stderr)

grow.cpp:239:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  239 | main()
      | ^~~~
grow.cpp: In function 'int main()':
grow.cpp:243:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  243 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
grow.cpp:244:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  244 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10