Submission #1224669

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224669		lkateris	Inside information (BOI21_servers)	C++20	0 / 100	19 ms	584 KiB

servers

#include <iostream>
#include <utility>

using namespace std;


pair<int,int> seg[480020];
pair<int,int> lazy[480020];
int N,K;

void Build(int start=1,int ende=N,int ind=1) {
    if (start == ende) {
        seg[ind].first = start;
        seg[ind].second = start;
        return;
    }
    int mid=(start+ende)/2;

    Build(start,mid,ind*2);
    Build(mid+1,ende,ind*2 + 1);
    return;
}

void Update(int from, int to,int vall,int valr,int start=1,int ende=N,int ind=1) {
    if (start==from and ende==to) {
        lazy[ind].first += vall;
        lazy[ind].second += valr;
        return;
    }

    int mid=(start+ende)/2;
    if (to <= mid) Update(from,to,vall,valr,start,mid,ind*2);
    else if (mid < from) Update(from,to,vall,valr,mid+1,ende,ind*2 + 1);
    else {
        Update(from,mid,vall,valr,start,mid,ind*2);
        Update(mid+1,to,vall,valr,mid+1,ende,ind*2 + 1);
    }
    return;
}

pair<int,int> Query(int pos,int start=1,int ende=N,int ind=1) {
    if (start == ende) {
        seg[ind].first += lazy[ind].first;
        seg[ind].second += lazy[ind].second;
        lazy[ind] = {0,0};
        return seg[ind];
    }

    int mid=(start+ende)/2;

    seg[ind].first += lazy[ind].first;
    seg[ind].second += lazy[ind].second;

    lazy[ind*2].first += lazy[ind].first;
    lazy[ind*2].second += lazy[ind].second;

    lazy[ind*2 + 1].first += lazy[ind].first;
    lazy[ind*2 + 1].second += lazy[ind].second;
    lazy[ind] = {0,0};

    if (pos <= mid) return Query(pos,start,mid,ind*2);
    else return Query(pos,mid+1,ende,ind*2 + 1);
}


int main() {


    scanf("%d%d",&N,&K);

    Build();

    for(int q=1;q<=N+K-1;++q) {
        char t;
        scanf(" \n%c",&t);
        if (t == 'S') {
            int a,b;
            scanf("%d%d",&a,&b);
            if (a > b) swap(a,b);
            pair<int,int> lra = Query(a);
            pair<int,int> lrb = Query(b);
            int l=1,r=lra.second;
            int res=lra.second;
            while (l <= r) {
                int mid = (l+r)/2;
                if (Query(mid).second == lra.second) {
                    res = min(res,mid);
                    r = mid-1;
                }
                else l = mid + 1;
            }
            Update(res,lra.second,0,1);
            printf("d\n");
            res=lrb.first;
            l=lrb.first,r=N;

            while (l <= r) {
                int mid = (l+r)/2;
                if (Query(mid).second == lrb.first) {
                    res = max(res,mid);
                    l = mid + 1;

                }
                else r = mid-1;
            }
            Update(lrb.first,res,-1,0);
        }
        else if (t == 'Q') {
            int a,d;
            scanf("%d%d",&a,&d);
            pair<int,int> lrd = Query(d);
            if (lrd.first <= a and a <=lrd.second) printf("yes\n");
            else printf("no\n");

        }
        else if (t == 'C') {
            int d;
            scanf("%d",&d);
            pair<int,int> lrd = Query(d);
            printf("%d\n",lrd.second-lrd.first+1);
        }
        else q--;

    }
    return 0;
}

Compilation message (stderr)

servers.cpp: In function 'int main()':
servers.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |     scanf("%d%d",&N,&K);
      |     ~~~~~^~~~~~~~~~~~~~
servers.cpp:75:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |         scanf(" \n%c",&t);
      |         ~~~~~^~~~~~~~~~~~
servers.cpp:78:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |             scanf("%d%d",&a,&b);
      |             ~~~~~^~~~~~~~~~~~~~
servers.cpp:110:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |             scanf("%d%d",&a,&d);
      |             ~~~~~^~~~~~~~~~~~~~
servers.cpp:118:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |             scanf("%d",&d);
      |             ~~~~~^~~~~~~~~

• Subtask 1-1: 0 / 2
• Subtask 1-2: 0 / 3
• Subtask 2-1: 0 / 2
• Subtask 2-2: 0 / 3
• Subtask 3-1: 0 / 5
• Subtask 3-2: 0 / 5
• Subtask 4-1: 0 / 10
• Subtask 4-2: 0 / 10
• Subtask 5-1: 0 / 12
• Subtask 5-2: 0 / 13
• Subtask 6-1: 0 / 17
• Subtask 6-2: 0 / 18