Submission #835849

#	Time	Username	Problem	Language	Result	Execution time	Memory
835849		YassirSalama	Meetings (IOI18_meetings)	C++17	0 / 100	24 ms	3284 KiB

meetings

#include "meetings.h"
#include<bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
using namespace std;
#define ll long long
#define OVL(v,s) for(auto x:v) cout<<x<<s;cout<<endl;
#define all(v) v.begin(),v.end()
#define F first
#define S second
#define pb push_back
void dbg_out() { cout << endl; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cout << ' ' << H; dbg_out(T...); }
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__);
#define endl "\n"
#define mod 1000000007
const ll INF=1e18;
const ll MAXN=1e5;
const ll LOGN=18;
struct Node1{
    ll sum=0;
    ll left=0;
    ll right=0;
    ll mx=0;
};
Node1 merge(Node1 a,Node1 b){
    Node1 c;
        c.left=max(a.left,a.sum+b.left);
        c.right=max(b.right,b.sum+a.right);
        c.sum=a.sum+b.sum;
        c.mx=max({a.mx,b.mx,a.right+b.left});
    return c;
}
struct Node{
   Node1 val;
   Node* left,*right;
   Node() : val({0,0,0,0}),left(nullptr),right(nullptr) {}
};
Node* root;
vector<ll> v;
ll n;
ll arr[MAXN];
void build(Node* node,ll l,ll r){
    if(l==r){
        node->val={arr[l],arr[l],arr[l],arr[l]};
        return;
    }
    ll mid=(l+r)/2;
    node->left=new Node();
    node->right=new Node();
    build(node->left,l,mid);
    build(node->right,mid+1,r);
    node->val=merge(node->left->val,node->right->val);
}
Node1 query(Node* node,ll l,ll r,ll ql,ll qr){
    if(ql<=l&&r<=qr) return node->val;
    Node1 ans;
    ll mid=(l+r)/2;
    // dbg(l,r);
    if(ql<=mid&&qr>mid){
        ans=merge(
                query(node->left,l,mid,ql,qr),
                query(node->right,mid+1,r,ql,qr)
            );
        return ans;
    }
    else if(ql<=mid) return query(node->left,l,mid,ql,qr);
    else return query(node->right,mid+1,r,ql,qr);
}
vector<long long> minimum_costs(vector<int> H, vector<int> L,vector<int> R) {
    n=H.size();
    for(auto x:H){
        v.push_back(x);
    }
    root = new Node();
    ll q=L.size();
    vector<ll> anss(q,10);
    for(ll i=0;i<n;i++){
        if(v[i]==2){
            arr[i]=-INF;
            continue;
        }
        else arr[i]=1;
    }
    build(root,0,n-1);
    for(ll i=0;i<q;i++){
        ll l=L[i];
        ll r=R[i];
        // dbg(l,r);
        ll Y=2*(r-l+1);
        ll a=query(root,0,n-1,l,r).mx;
        anss[i]=-max(0LL,a)+Y;
    }
    // dbg(query(root,0,n-1,2,4).mx);
    return anss;
}



#ifdef IOI
#include <cstdio>
#include <cstdlib>
#include <vector>
#include "meetings.h"

namespace {

ll read_int() {
  ll x;
  if (scanf("%lld", &x) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  return x;
}

}  // namespace

signed main() {
  ll N = read_int();
  ll Q = read_int();
  std::vector<int> H(N);
  for (int i = 0; i < N; ++i) {
    H[i] = read_int();
  }
  std::vector<int> L(Q), R(Q);
  for (ll j = 0; j < Q; ++j) {
    L[j] = read_int();
    R[j] = read_int();
  }

  std::vector<long long> C = minimum_costs(H, L, R);
  for (size_t j = 0; j < C.size(); ++j) {
    printf("%lld\n", C[j]);
  }
  return 0;
}

#endif


// ll lg[MAXN];
// ll st[MAXN][LOGN];
// //sparse table
// void build(){
//     for(ll i=0;i<n;i++) st[i][0]=v[i];
//     for(ll j=1;j<LOGN;j++){
//         for(ll i=0;i+(1<<j)<=n;i++){
//             st[i][j]=max(
//                     st[i][j-1],
//                     st[i+(1<<(j-1))][j-1]
//                 );
//         }
//     }
//     lg[1]=0;
//     for(ll i=2;i<MAXN;i++){
//         lg[i]=lg[i/2]+1;
//     }
// }
// ll query(ll l,ll r){
//     ll k=r-l+1;
//     k=lg[k];
//     return max(
//             st[l][k],
//             st[r-(1<<k)+1][k]
//         );
// }

• Subtask 1: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40