제출 #1046519

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1046519		Requiem	Sails (IOI07_sails)	C++17	100 / 100	224 ms	12632 KiB

sails

#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 endl "\n"
#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 pi 3.14159265359
#define TASKNAME "sails"
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; }
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;

/**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) {};
};
/*--------------------------------*/

const int MAXN = 1e5 + 9;

struct Poles{  //cây cột chứa các sail
     int height, numSail;
} P[MAXN];

int n;

void input(){
   cin >> n;
   for(int i = 1; i <= n; i++){
       cin >> P[i].height >> P[i].numSail;
   }
    sort(P + 1, P + 1 + n, [&](const Poles &a, const Poles &b){
         return (a.height == b.height) ? (a.numSail < b.numSail) : (a.height < b.height);
    });
}

namespace subtask1{
    bool check(){
         return n <= 200;
    }

    vector<int> state[MAXN];
    int ans = inf;
    map<int, int> cnt;

    int calc(){
        cnt.clear();
        int sum = 0;
        for(int i = n; i >= 1; i--){
            for(auto x: state[i]){
                sum += cnt[x];
                cnt[x]++;
            }
        }
        return sum;
    }

    void backtrack(int pos, int numChosen, int last){
         if (pos == n + 1){
             minimize(ans, calc());
             return;
         }

         if (numChosen < P[pos].numSail){
             for(int j = last + 1; j <= P[pos].height; j++){
                 state[pos].pb(j);
                 backtrack(pos, numChosen + 1, j);
                 state[pos].pop_back();
             }
         }
         else{
             backtrack(pos + 1, 0, 0);
         }
    }
    void solve(){
         backtrack(1, 0, 0);
         cout << ans << endl;
    }
}

/**
 * IOI 2007 Sail Solution:
 * bài này mình đang suy nghĩ đến việc tham lam.
 * Với 1 thằng, ta sẽ cố chọn những thằng cao nhất có thể chưa được chọn vì nó là tốt nhất
 * Xét đến vị trí i, liệu kết quả của ta có xuất phát từ vị trí i + 1 hay không.
 *
 * Ưu tiên số 1: Rải đều ra.
 * ƯU tiên số 2: chọn càng cao càng tốt.
 *
 * ==> Thuật sai
 *
 * Giả sử ta có x sail nằm thẳng hàng thì cost của ta là bao nhiêu?
 * Ta sẽ có cost là x * (x - 1) / 2
 * Giả sử cuối cùng, ta có 1 cấu hình sao cho thằng i chứa cnt[i] thằng thì tổng cộng ta sẽ có cost là cnt[i] * (cnt[i] - 1) / 2.
 * Đây là hàm bình phương nên dễ hiểu khi ta cố trải đều nó ra.
 * Từ hàm tính cost trên, ta thấy rằng thứ tự của các sail là không quan trọng và ta có thể sort nó theo độ cao.
 *
 */
namespace subtask2{
    bool check(){
        return n <= 2000;
    }

    int cnt[MAXN];
    ii temp[MAXN];

    void solve(){
        int ans1 = 0;

        int ans2 = 0;
        memset(cnt, 0, sizeof(cnt));
        for(int i = 1; i <= n; i++){
            for(int j = P[i].height; j >= 1; j--){
                temp[j] = {cnt[j], j};
            }
            sort(temp + 1, temp + 1 + P[i].height);
            for(int j = 1; j <= P[i].numSail; j++){
                ans2 += temp[j].fi;
                cnt[temp[j].se]++;
            }
        }
        cout << ans2 << endl;
    }
}

/**
 * Ta mò ra được subtask 2 là thuật đúng, h ta chỉ cần tối ưu nó lên.
   Subtask 2:
   Ta sort lại các cột theo độ cao
   Duyệt các cột từ 1 đến n.
   Tại cột i:
   * ta tìm tổng P[i].numSail giá trị nhỏ nhất trong đoạn [l, r].
   * Cập nhật các vị trí đó lên.
   Lưu ý là ta duyệt từ cột thấp đến cột cao, ta sẽ cố áp dụng kĩ thuật duy trì order như bài grow.
   Cây segment tree của ta cần hỗ trợ điều gì?
   Gọi cnt là numSail tại vị trí i.
   - Truy vấn tính tổng của cnt số nhỏ nhất. Ta sẽ tính tổng của cnt số nhỏ nhất xuất phát từ P[i].sail
   - Khi cập nhật chắc chắn ta sẽ cập nhật cnt số từ cuối. Tương tự với bài grow, ta sẽ gọi max là giá
   trị lớn nhất được cập nhật, ta sẽ tìm vị trí đầu tiên có giá trị nhỏ hơn nó (về bên phải) và cập nhật đoạn đó trước
   sau đó ta tìm vị trí xuất hiện cuối cùng của giá trị max rồi cập nhật từ đó trở đi (như bài grow).
**/
namespace subtask3{
    bool check(){
         return true;
    }

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

    void mergeNode(ITnode &res, ITnode a, ITnode b){
        res.sumRange = (a.sumRange + b.sumRange);
        res.minRange = min(a.minRange, b.minRange);
    }

    void fix(int nn, int l, int r){
        IT[nn].sumRange += (r - l + 1) * IT[nn].lazy;
        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){
        fix(nn, l, r);
        if (l >= u and r <= v){
            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 * 2], IT[nn * 2 + 1]);
    }

    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]);
             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 findFirstLower(int nn, int l, int r, int u, int v, int k){
        fix(nn, l, r);
        int mid = (l + r) >> 1;
        if (l >= u and r <= v){
//            debug(IT[nn].minRange, l, r, u, v, 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].minRange < k) return findFirstLower(nn << 1, l, mid, u, v, k);
            else return findFirstLower(nn << 1 | 1, mid + 1, r, u, v, k);
        }
        if (l > v or r < u) return 0;
        int g1 = findFirstLower(nn << 1, l, mid, u, v, k);
        int g2 = findFirstLower(nn << 1 | 1, mid + 1, r, u, v, k);
        return ((!g1) ? g2 : g1);
    }

    ITnode getRange(int l, int r){
        ITnode res = {0, (int) inf, 0};
        getRange(1, 1, maxHeight, l, r, res);
        return res;
    }
    void updateRange(int l, int r, int k){
        updateRange(1, 1, maxHeight, l, r, k);
    }
    int findFirstLower(int l, int r, int k){
        return findFirstLower(1, 1, maxHeight, l, r, k);
    }
    void solve(){
        for(int i = 1; i <= n; i++){
            maximize(maxHeight, P[i].height);
//            debug(P[i].height, P[i].numSail);
        }

//        debug(maxHeight);
        int ans = 0;
        for(int i = 1; i <= n; i++){
            int numNeed = P[i].numSail;
            ans += getRange(P[i].height - P[i].numSail + 1, P[i].height).sumRange;

            int l = P[i].height - P[i].numSail + 1;
            int r = P[i].height;
//            debug(l, r, getRange(l, r).sumRange);

            int curMx = getRange(l, l).minRange;
//            debug(curMx);

            int forward = findFirstLower(l, r, curMx);
//            debug(l, r, curMx);
            if (forward != 0){
                updateRange(forward, r, 1);
//                debug(forward, r);
            }
            else forward = r + 1;
            int numMx = forward - l;

            int backward = findFirstLower(1, maxHeight, curMx + 1);
//            debug(numMx, forward, backward);
            updateRange(backward, backward + numMx - 1, 1);
//            debug(backward, backward + numMx - 1);

        }
        cout << ans << endl;
    }
}
void solve(){
//    if (subtask1::check()) return subtask1::solve();
//     if (subtask2::check()) return subtask2::solve();
     if (subtask3::check()) return subtask3::solve();
}
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
**/

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

sails.cpp: In function 'void subtask2::solve()':
sails.cpp:157:13: warning: unused variable 'ans1' [-Wunused-variable]
  157 |         int ans1 = 0;
      |             ^~~~
sails.cpp: In function 'void subtask3::solve()':
sails.cpp:280:17: warning: unused variable 'numNeed' [-Wunused-variable]
  280 |             int numNeed = P[i].numSail;
      |                 ^~~~~~~
sails.cpp: At global scope:
sails.cpp:313:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  313 | main()
      | ^~~~
sails.cpp: In function 'int main()':
sails.cpp:317:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  317 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
sails.cpp:318:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  318 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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