제출 #1025589

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1025589		thdh__	새로운 문제 (POI11_met)	C++17	74 / 100	449 ms	47528 KiB

met

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define eb emplace_back
#define pu push
#define ins insert
#define bruh ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ff(x,a,b,c) for (auto x=a;x<=b;x+=c)
#define fd(x,a,b,c) for (auto x=a;x>=b;x-=c)
#define int ll

using namespace std;
//mt19937 mt(chrono::steady_clock::now().time_since_epoch().count());

typedef pair<int, int> ii;
const int N = 3e5+5;
const int mod = 1e9+7;
const int INF = 1e18;
using cd = complex<double>;
const long double PI = acos(-1);
int power(int a,int b) {ll x = 1;if (a >= mod) a%=mod; while (b) {if (b & 1) x = x*a % mod;a = a*a % mod;b>>=1;}return x;} 

struct bit {
    int n,b[N];
    void init(int _)
    {
        n = _; 
        for (int i=1;i<=n;i++) b[i] = 0;
    }
    void upd(int x,int v)
    {
        for (;x<=n;x += x&(-x)) b[x] += v;
    }
    int get(int x)
    {
        int sum = 0;
        for (;x>0;x -= x&(-x)) sum += b[x];
        return sum;
    }
    void update(int l,int r,int v)
    {
        upd(r+1,-v), upd(l,v);
        if(l>r) upd(1,v);
    }
} BIT;

int n,m,k;
vector<int> o[N];
int p[N];
vector<array<int,3>> event;
int ans[N];

void PBS(int l,int r,vector<int>& mem)
{
    if (l==r-1 || !mem.size())
    {
        for (auto i : mem) ans[i] = l;
        return;
    }
    int mid = (l+r)/2;
    //calculate [l,mid]
    for (int i=l;i<mid;i++)
    {
        auto cur_event = event[i];
        int cl = cur_event[0],cr = cur_event[1],ca = cur_event[2];
        BIT.update(cl,cr,ca);
    }
    vector<int> p1,p2; // members in the first half and second half
    for (auto c : mem)
    {
        int sum = 0;
        for (auto i : o[c]) sum += BIT.get(i);
        if (sum >= p[c]) p1.pb(c);
        else p2.pb(c),p[c]-=sum;
    }
    //undo
    for (int i=l;i<mid;i++)
    {
        auto cur_event = event[i];
        int cl = cur_event[0],cr = cur_event[1],ca = cur_event[2];
        BIT.update(cl,cr,-ca);
    }
    PBS(l,mid,p1); p1.clear();
    PBS(mid,r,p2); p2.clear();
}

void solve()
{
	cin>>n>>m;
    BIT.init(m);
    for (int i=1;i<=m;i++) 
    {
        int x; cin>>x; o[x].pb(i);
    }
    for (int i=1;i<=n;i++) cin>>p[i];
    cin>>k;
    for (int i=0;i<k;i++) 
    {
        int l,r,a; cin>>l>>r>>a;
        event.pb({l,r,a});
    }
    vector<int> tmp;
    for (int i=1;i<=n;i++) tmp.pb(i);
    PBS(0,k+1,tmp);
    for (int i=1;i<=n;i++)
    {
        if (ans[i]==k) cout<<"NIE";
        else cout<<ans[i]+1;
        cout<<endl;
    }
}

signed main()
{
	bruh
	//freopen("input.inp","r",stdin);
	//freopen("output.inp","w",stdout);
	int t = 1;
	//cin>>t;
	while (t--)
	{
		solve();
		cout<<"\n";
	}
}

• Subtask 1: 12 / 12
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 12 / 12
• Subtask 5: 13 / 13
• Subtask 6: 13 / 13
• Subtask 7: 0 / 13
• Subtask 8: 0 / 13