Submission #835824

#	Time	Username	Problem	Language	Result	Execution time	Memory
835824		YassirSalama	Meetings (IOI18_meetings)	C++17	Compilation error	0 ms	0 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
#define abcdef int
#define int long long
const ll INF=1e18;
const int MAXN=1e5;
const int LOGN=18;
struct Node1{
    int sum=0;
    int left=0;
    int right=0;
    int mx=0;
    merge(Node1 a,Node1 b){
        left=max(a.left,a.sum+b.left);
        right=max(b.right,b.sum+a.right);
        sum=a.sum+b.sum;
        mx=max({a.mx,b.mx,a.right+b.left});
    }
};
struct Node{
   Node1 val;
   Node* left,*right;
   Node() : val({0,0,0,0}),left(nullptr),right(nullptr) {}
};
Node* root;
vector<ll> v;
int n;
int arr[MAXN];
void build(Node* node,int l,int r){
    if(l==r){
        node->val={
            .sum=arr[l],
            .left=arr[l],
            .right=arr[l],
            .mx=arr[l],
        };
        return;
    }
    int 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,int l,int r,int ql,int qr){
    if(ql<=l&&r<=qr) return node->val;
    Node1 ans;
    int 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<abcdef> H, vector<abcdef> L,vector<abcdef> R) {
    n=H.size();
    for(auto x:H){
        v.push_back(x);
    }
    root = new Node();
    int q=L.size();
    vector<ll> anss(q,10);
    for(int i=0;i<n;i++){
        if(v[i]==2){
            arr[i]=-INF;
            continue;
        }
        else arr[i]=1;
    }
    build(root,0,n-1);
    for(int i=0;i<q;i++){
        int l=L[i];
        int r=R[i];
        // dbg(l,r);
        int Y=2*(r-l+1);
        int a=query(root,0,n-1,l,r).mx;
        anss[i]=min(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 {

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

}  // namespace

signed main() {
  int N = read_int();
  int 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 (int 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(int i=0;i<n;i++) st[i][0]=v[i];
//     for(int j=1;j<LOGN;j++){
//         for(int 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(int i=2;i<MAXN;i++){
//         lg[i]=lg[i/2]+1;
//     }
// }
// int query(int l,int r){
//     int k=r-l+1;
//     k=lg[k];
//     return max(
//             st[l][k],
//             st[r-(1<<k)+1][k]
//         );
// }

Compilation message (stderr)

meetings.cpp:27:5: error: ISO C++ forbids declaration of 'merge' with no type [-fpermissive]
   27 |     merge(Node1 a,Node1 b){
      |     ^~~~~
meetings.cpp: In member function 'int Node1::merge(Node1, Node1)':
meetings.cpp:32:5: warning: no return statement in function returning non-void [-Wreturn-type]
   32 |     }
      |     ^