제출 #1347725

#제출 시각아이디문제언어결과실행 시간메모리
1347725Faisal_Saqib돌 무게 재기 (IZhO11_stones)C++20
0 / 100
62 ms3708 KiB
// #include <iostream>
// #include <bitset>
// #include <vector>
// using namespace std;
// typedef long long ll;
// bitset<100009> dp;
// void solve()
// {
//     int n;
//     cin>>n;
//     vector<int> a(n);
//     vector<int> pos(n);
//     for(int i=0;i<n;i++)
//     {
//         pos[i]=1;
//         cin>>a[i];
//     }
//     for(int i=0;i<n;i++)
//     {
//         dp.reset();
//         dp[0]=1;
//         int tot=0;
//         for(int j=i;j<n;j++)
//         {
//             dp|=(dp<<a[j]);
//             tot+=a[j];
//             if(tot%2==0 and dp[tot/2])
//             {
//             }
//             else{
//                 pos[j-i]=0;
//             }
//         }
//     }
//     int cnt=0;
//     for(int i=0;i<n;i++)cnt+=pos[i];
//     cout<<cnt<<' ';
//     for(int j=0;j<n;j++)if(pos[j])cout<<j+1<<' ';
//     cout<<endl;
// }
// int main()
// {
//     ios::sync_with_stdio(0);
//     cin.tie(0);
//     cout.tie(0);
//     int t;
//     cin>>t;
//     while(t--)
//     {
//         solve();
//     }
// }
#include <iostream>
using namespace std;
typedef long long ll;
const int N=100009;
int lzy[N<<2],mx[N<<2],mi[N<<2];
int n;
void push(int l,int r,int v)
{
    mx[v]+=lzy[v];
    mi[v]+=lzy[v];
    if(l!=r)lzy[2*v]+=lzy[v],lzy[2*v+1]+=lzy[v];
    lzy[v]=0;
}
void add(int ql,int qr,int qv,int l=1,int r=n,int v=1)
{
    push(l,r,v);
    if(qr<l or r<ql)return;
    if(ql<=l and r<=qr)
    {
        lzy[v]+=qv;
        push(l,r,v);
        return;
    }
    int m=(l+r)>>1,lc=v<<1,rc=lc|1;
    add(ql,qr,qv,l,m,lc);
    add(ql,qr,qv,m+1,r,rc);
    mx[v]=max(mx[lc],mx[rc]);
    mi[v]=min(mi[lc],mi[rc]);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int w,t;
        cin>>w>>t;
        if(t==2)t=-1;
        add(1,w,t);
        int mx1=mx[1],mi1=mi[1];
        if(mx1==0)
        {
            cout<<'<'<<endl;
        }
        else if(mi1==0)
        {
            cout<<'>'<<endl;
        }
        else
        {
            cout<<'?'<<endl;
        }
    }
}
#Verdict Execution timeMemoryGrader output
Fetching results...