12769 - Kool Konstructions

[Repon kumar Roy]

I am getting TLE...
I am using normal array manupulation....

Let me know what type of data structure to be used

[Repon kumar Roy]

Again TLE....
Please suggest me..

Code: Select all

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<iterator>
#include<cassert>

using namespace std;

/*------- Constants---- */
#define MX 100000
#define ll long long
#define ull unsigned long long
#define mod 1000000007

/* -------Global Variables ------ */
ll x,y,d;

/*---- short Cuts ------- */
#define ms(ara_name,value) memset(ara_name,value,sizeof(ara_name))



typedef struct s{
    ll strt,end,incre;
}tower;
vector<ll>number_piller;
vector<tower> anm;
queue<ll>pos;
ll ara[MX+1],hieght[MX+1];


int main()
{
    ll query,a,b,y,i,murgi,flag,putput;
    tower tmp;
    char ins;
    vector<ll>::iterator it;
    while (scanf("%lld",&query)==1 && query) {
        if(query==0) break;
        i=0;
        //queue<ll> pos;
        while (i<query) {
            while ((ins=getchar())=='\n');
            if(ins=='B'){
                cin>>a>>b>>y;
                tmp.strt=a;tmp.end = b;
                tmp.incre=y;
                anm.push_back(tmp);
            }
            else {
                cin>>a;
                pos.push(anm.size()-1);
                if(ara[a]==0){
                    number_piller.push_back(a);
                }
                ara[a]++;
                
            }
            i++;
        }
        sort(number_piller.begin(), number_piller.end());
        putput = pos.front();
        pos.pop();
        for (i=0; i<anm.size(); i++) {
            
            a= anm[i].strt ;
            b = anm[i].end;
            murgi=anm[i].incre;
            ll low=0,high=number_piller.size(),mid;
            while (low<=high) {
                mid= (low+high)/2;
                if(a== number_piller[mid]) {
                    flag=1;
                    break;
                }
                else if (a>number_piller[mid]) low = mid+1;
                else high = mid-1;
            }
            if(flag) x= low;
            else x = low+1;
            for (; x<number_piller.size() &&  b>=number_piller[x]; x++) {
                hieght[number_piller[x]]+= murgi;
            }
            if(i==putput){
                a = number_piller.front();
                ara[a]--;
                printf("%lld\n",hieght[a]);
                if(ara[a]==0){
                    //it=upper_bound(number_piller.begin(), number_piller.end(), a);
                    low=0,high=number_piller.size(),mid;
                    while (low<=high) {
                        mid= (low+high)/2;
                        if(a== number_piller[mid]) {
                            x=mid;
                            break;
                        }
                        else if (a>number_piller[mid]) low = mid+1;
                        else high = mid-1;
                    }
                    number_piller.erase(number_piller.begin()+x);
                }
                if(pos.empty()) break;
                putput = pos.front();
                pos.pop();
                
            }
        }
        
        anm.clear();
        number_piller.clear();
        ms(hieght, 0);
        ms(ara, 0);
    }
    return 0;
}

[brianfry713]

I solved it using square root decomposition.