oj.uz

답안 #794732

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
794732 2023-07-26T20:28:03 Z merlin 모임들 (IOI18_meetings) C++14
17 / 100
 82 ms 12360 KB 
#include<bits/stdc++.h>
#include "meetings.h"
using namespace std;
#define ll long long
#define f first
#define s second

void setIO(string name="") {
	cin.tie(0)->sync_with_stdio(0);
	if (!name.empty()) {
		freopen((name+".in").c_str(), "r", stdin);
		freopen((name+".out").c_str(), "w", stdout);
	}
}

struct info{
    int best,le,ri,len;
    info() : best(0),le(0),ri(0),len(0){};
    info(int x) : best(x == 1), le(x==1),ri(x==1),len(1){};
};

struct Tree{
    int n=1;
    vector<int> left,right;
    vector<info> vals;
    info combine(info a,info b){ //val, left, right
        info ans;
        ans.best = max(a.best,max(b.best,a.ri + b.le));
        if(a.len == a.best)
            ans.le = a.best + b.le;
        else 
            ans.le = a.le;
        if(b.len == b.best)
            ans.ri = b.best + a.ri;
        else
            ans.ri = b.ri;
        ans.len = a.len + b.len;
        return ans;
    }
    Tree(int sz,vector<int> &v){
        while(n < sz)n*=2;
        vals = vector<info>(2*n);
        left = right = vector<int>(2*n,0);
        for(int i = 0;i<n;i++){
            left[i+n] = i;
            right[i+n] = i+1;
            if(i < sz){
                vals[i+n] = info(v[i]);
            }
        }
        for(int i = n-1;i;i--){
            left[i] = left[i*2];
            right[i] = right[i*2+1];
            vals[i] = combine(vals[i*2],vals[i*2+1]);
        }
    }
    int range_query(int l,int r){
        //cerr<<"wtfff "<<l<<" "<<r<<endl;
        info tmp = range_query(l,r,1);
        return tmp.best;
    }
    info range_query(int l,int r,int cur){
        //cerr<<cur<<" "<<l<<" "<<r<<" "<<left[cur]<<" "<<right[cur]<<" ";
        if(l >= right[cur] || r <= left[cur]){
            //cerr<<"mimo"<<endl;
            return info();
        }
        if(l <= left[cur] && r >= right[cur]){
            //cerr<<"cely in"<<endl;
            return vals[cur];
        }
        //cerr<<"divne"<<endl;
        return combine(range_query(l,r,cur*2),range_query(l,r,cur*2+1));
    }
};

vector<ll> minimum_costs(vector<int> H,vector<int> L,vector<int> R){
    int q = L.size(),n = H.size();
    if(0 && n <= 3000 && q <= 10){
        vector<ll> anss;
        for(int Q = 0;Q<q;Q++){
            ll ans = 1e16;
            for(int i = L[Q];i<=R[Q];i++){
                ll tmp = H[i];
                ll mx = H[i];
                for(int j = i+1;j <= R[Q];j++){
                    mx = max(mx,(ll)H[j]);
                    tmp += mx;
                }
                mx = H[i];
                for(int j = i-1;j >= L[Q];j--){
                    mx = max(mx,(ll)H[j]);
                    tmp += mx;
                }
                ans = min(ans,tmp);
            }
            anss.push_back(ans);
        }
        return anss;
    }
    vector<int> tmp;
    for(auto i : H) tmp.push_back(i == 1 ? 1 : 0);
    Tree tr(n,tmp);
    //for(int i = 1;i < 2*tr.n;i++)cerr<<i<<" "<<tr.vals[i]<<" "<<tr.l_vals[i]<<" "<<tr.r_vals[i]<<endl;
    vector<ll> ans;
    for(int i = 0;i<q;i++){
        //cerr<<L[i]<<" "<<R[i]<<endl;
        //cerr<<"xd "<<tr.range_query(L[i],R[i]+1)<<endl;
        ans.push_back(2*(R[i] - L[i] + 1) - tr.range_query(L[i],R[i]+1));
    }
    return ans;
}

Compilation message

meetings.cpp: In function 'void setIO(std::string)':
meetings.cpp:11:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |   freopen((name+".in").c_str(), "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
meetings.cpp:12:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |   freopen((name+".out").c_str(), "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 4.0

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

Subtask #2
0 / 15.0

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

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 26 ms 2104 KB Output is correct
3 Correct 76 ms 12308 KB Output is correct
4 Correct 82 ms 12360 KB Output is correct
5 Correct 58 ms 12336 KB Output is correct
6 Correct 72 ms 12344 KB Output is correct
7 Correct 77 ms 12336 KB Output is correct

Subtask #4
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 26 ms 2104 KB Output is correct
3 Correct 76 ms 12308 KB Output is correct
4 Correct 82 ms 12360 KB Output is correct
5 Correct 58 ms 12336 KB Output is correct
6 Correct 72 ms 12344 KB Output is correct
7 Correct 77 ms 12336 KB Output is correct
8 Incorrect 77 ms 12328 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 40.0

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