oj.uz

Submission #260941

# Submission time Handle Problem Language Result Execution time Memory
260941 2020-08-11T08:19:01 Z 최은수(#5044) Sweeping (JOI20_sweeping) C++17
10 / 100
 7612 ms 605780 KB 
#include<iostream>
#include<vector>
#include<set>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
struct seg
{
    set<int>t[4000010];
    void upd(int n,int s,int e,int x,int p)
    {
        t[n].ep(p);
        if(s==e)
            return;
        int m=s+(e-s)/2;
        if(x>m)
            upd(n*2+1,m+1,e,x,p);
        else
            upd(n*2,s,m,x,p);
        return;
    }
    int query(int n,int s,int e,int S,int E,int p)
    {
        if(s>E||S>e)
            return inf;
        if(S<=s&&e<=E)
        {
            auto it=t[n].lower_bound(p);
            return it==t[n].end()?inf:*it;
        }
        int m=s+(e-s)/2;
        return min(query(n*2,s,m,S,E,p),query(n*2+1,m+1,e,S,E,p));
    }
}st;
pi pos[1500010];
int when[1500010];
int pct;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,q;
    cin>>n>>m>>q;
    pct=m;
    for(int i=0;i++<m;)
    {
        cin>>pos[i].fi>>pos[i].se;
    }
    for(int i=0;i++<q;)
    {
        int t,l;
        cin>>t>>l;
        if(t==1)
        {
            if(when[l]==i-1)
                cout<<pos[l].fi<<' '<<pos[l].se<<'\n';
            else
                cout<<max(pos[l].fi,n-st.query(1,1,q,when[l]+1,i-1,pos[l].se))<<' '<<pos[l].se<<'\n';
        }
        else if(t==2)
        {
            st.upd(1,1,q,i,l);
        }
        else if(t==3)
        {
        }
        else
        {
            when[++pct]=i;
            pos[pct].fi=l;
            cin>>pos[pct].se;
        }
    }
    cout.flush();
    return 0;
}

Subtask #1
0 / 1.0

# Verdict Execution time Memory Grader output
1 Incorrect 109 ms 188408 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7281 ms 597760 KB Output is correct
2 Correct 7170 ms 597996 KB Output is correct
3 Correct 7035 ms 597656 KB Output is correct
4 Correct 4267 ms 605780 KB Output is correct
5 Correct 4116 ms 597152 KB Output is correct
6 Correct 5854 ms 597616 KB Output is correct
7 Correct 7612 ms 598008 KB Output is correct

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 7169 ms 595820 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Incorrect 7169 ms 595820 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 109 ms 188408 KB Output isn't correct
2 Halted 0 ms 0 KB -